{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Accepted Invitations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #backtracking #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #回溯 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumInvitations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最多邀请的个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>某一个班级有 <code>m</code> 个男孩和 <code>n</code> 个女孩，即将举行一个派对。</p>\n",
    "\n",
    "<p>给定一个 <code>m x n</code> 的整数矩阵 <code>grid</code> ，其中 <code>grid[i][j]</code> 等于 <code>0</code> 或 <code>1</code> 。 若 <code>grid[i][j] == 1</code> ，则表示第 <code>i</code> 个男孩可以邀请第 <code>j</code> 个女孩参加派对。 一个男孩最多可以邀请<strong>一个女孩</strong>，一个女孩最多可以接受一个男孩的<strong>一个邀请</strong>。</p>\n",
    "\n",
    "<p>返回可能的最多邀请的个数。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><b>示例 1:</b></p>\n",
    "\n",
    "<pre><strong>输入:</strong> grid = [[1,1,1],\n",
    "               [1,0,1],\n",
    "               [0,0,1]]\n",
    "<strong>输出:</strong> 3<strong>\n",
    "解释:</strong> 按下列方式邀请：\n",
    "- 第 1 个男孩邀请第 2 个女孩。\n",
    "- 第 2 个男孩邀请第 1 个女孩。\n",
    "- 第 3 个男孩邀请第 3 个女孩。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> grid = [[1,0,1,0],\n",
    "               [1,0,0,0],\n",
    "               [0,0,1,0],\n",
    "               [1,1,1,0]]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释: </strong>按下列方式邀请：\n",
    "- 第 1 个男孩邀请第 3 个女孩。\n",
    "- 第 2 个男孩邀请第 1 个女孩。\n",
    "- 第 3 个男孩未邀请任何人。\n",
    "- 第 4 个男孩邀请第 2 个女孩。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>grid.length == m</code></li>\n",
    "\t<li><code>grid[i].length == n</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 200</code></li>\n",
    "\t<li><code>grid[i][j]</code> 是 <code>0</code> 或 <code>1</code> 之一。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-accepted-invitations](https://leetcode.cn/problems/maximum-number-of-accepted-invitations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-accepted-invitations](https://leetcode.cn/problems/maximum-number-of-accepted-invitations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,1],[1,0,1],[0,0,1]]', '[[1,0,1,0],[1,0,0,0],[0,0,1,0],[1,1,1,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        def max_cycle(fa: List[int]) -> int:\n",
    "            n = len(fa)\n",
    "            vis = [False] * n\n",
    "            ans = 0\n",
    "            for i in range(n):\n",
    "                if vis[i]:\n",
    "                    continue\n",
    "                cycle = []\n",
    "                j = i\n",
    "                while not vis[j]:\n",
    "                    cycle.append(j)\n",
    "                    vis[j] = True\n",
    "                    j = fa[j]\n",
    "                for k, v in enumerate(cycle):\n",
    "                    if v == j:\n",
    "                        ans = max(ans, len(cycle) - k)\n",
    "                        break\n",
    "            return ans\n",
    "\n",
    "        def topological_sort(fa: List[int]) -> int:\n",
    "            n = len(fa)\n",
    "            indeg = [0] * n\n",
    "            dist = [1] * n\n",
    "            for v in fa:\n",
    "                indeg[v] += 1\n",
    "            q = deque(i for i, v in enumerate(indeg) if v == 0)\n",
    "            while q:\n",
    "                i = q.popleft()\n",
    "                dist[fa[i]] = max(dist[fa[i]], dist[i] + 1)\n",
    "                indeg[fa[i]] -= 1\n",
    "                if indeg[fa[i]] == 0:\n",
    "                    q.append(fa[i])\n",
    "            return sum(dist[i] for i, v in enumerate(fa) if i == fa[fa[i]])\n",
    "\n",
    "        return max(max_cycle(favorite), topological_sort(favorite))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n = len(favorite)\n",
    "        # 统计入度，便于进行拓扑排序\n",
    "        indeg = [0] * n\n",
    "        for i in range(n):\n",
    "            indeg[favorite[i]] += 1\n",
    "        \n",
    "        used = [False] * n\n",
    "        f = [1] * n\n",
    "        q = deque(i for i in range(n) if indeg[i] == 0)\n",
    "        \n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            used[u] = True\n",
    "            v = favorite[u]\n",
    "            # 状态转移\n",
    "            f[v] = max(f[v], f[u] + 1)\n",
    "            indeg[v] -= 1\n",
    "            if indeg[v] == 0:\n",
    "                q.append(v)\n",
    "        \n",
    "        # ring 表示最大的环的大小\n",
    "        # total 表示所有环大小为 2 的「基环内向树」上的最长的「双向游走」路径之和\n",
    "        ring = total = 0\n",
    "        for i in range(n):\n",
    "            if not used[i]:\n",
    "                j = favorite[i]\n",
    "                # favorite[favorite[i]] = i 说明环的大小为 2\n",
    "                if favorite[j] == i:\n",
    "                    total += f[i] + f[j]\n",
    "                    used[i] = used[j] = True\n",
    "                # 否则环的大小至少为 3，我们需要找出环\n",
    "                else:\n",
    "                    u = i\n",
    "                    cnt = 0\n",
    "                    while True:\n",
    "                        cnt += 1\n",
    "                        u = favorite[u]\n",
    "                        used[u] = True\n",
    "                        if u == i:\n",
    "                            break\n",
    "                    ring = max(ring, cnt)\n",
    "        \n",
    "        return max(ring, total)\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        # 找出所有的环\n",
    "        num = len(favorite) # 员工个数\n",
    "        # 广度优先遍历，找出除了环之外的结构，并且积累f[i]\n",
    "        # f[i]: 以节点i为终点的最长路径（含i的节点个数），f[i] = max_j2i{f[j]}, if 不存在j->i, f[i]=1\n",
    "        # 广度优先遍历的时候，环上的点是入队列的，所有f[i]的路径全部不途经任何环\n",
    "        dp = [1]*num # f[i]\n",
    "        indeg = [0] *num # 第i个人被多少人喜欢\n",
    "        \n",
    "        for i in range(num):\n",
    "            indeg[favorite[i]] += 1 \n",
    "        queue = [i for i in range(num) if indeg[i]==0 ] # 没有别人喜欢他（指向他）\n",
    "        \n",
    "        # 广度优先遍历\n",
    "        visit = [0]*num\n",
    "        \n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            visit[cur] = 1\n",
    "            cur_favor = favorite[cur]\n",
    "            # 更新dp\n",
    "            dp[cur_favor] = max(dp[cur_favor], dp[cur]+1) # 环上的点不会喜欢环外的点！parent有环，因为cur不在环上，路径上不会有别的环上的点\n",
    "            indeg[cur_favor] -= 1\n",
    "            if indeg[cur_favor] == 0:\n",
    "                queue.append(cur_favor)\n",
    "        print(favorite)\n",
    "        print(visit)\n",
    "\n",
    "        # 这种机制下不存在无环的情况\n",
    "        # 如果是2环，积累下来，cumu = f[x] + f[y]\n",
    "        # 如果是>2环，算最大节点数\n",
    "        cnt, cnt2 = 0, 0\n",
    "        for i in range(num):\n",
    "            if visit[i] == 1: continue # 浏览过的不重复浏览，不是环的都已经浏览过了\n",
    "            j = favorite[i]\n",
    "            if favorite[j] == i: # 环为2\n",
    "                cnt2 += dp[i] + dp[j]\n",
    "                visit[i] = 1\n",
    "                visit[j] = 1\n",
    "            else:\n",
    "                head = i\n",
    "                tmp_cnt = 0\n",
    "                while True:\n",
    "                    tmp_cnt += 1\n",
    "                    visit[i] = 1\n",
    "                    i = favorite[i]\n",
    "                    if i == head: break\n",
    "                cnt = max(cnt, tmp_cnt)\n",
    "        return max(cnt, cnt2)\n",
    "        \n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: list[int]) -> int:\n",
    "        n=len(favorite)\n",
    "        deg=[0]*n\n",
    "        for i in favorite:\n",
    "            deg[i]+=1\n",
    "        branch=deque(i for i,j in enumerate(deg) if j==0)\n",
    "        tree=[[] for i in range(n)]\n",
    "        while branch:\n",
    "            x=branch.popleft()\n",
    "            y=favorite[x]\n",
    "            deg[y]-=1\n",
    "            if deg[y]==0:\n",
    "                branch.append(y)\n",
    "            tree[y].append(x)\n",
    "        res=0\n",
    "        im=[]\n",
    "        for i in range(n):\n",
    "            if deg[i]==0:\n",
    "                continue\n",
    "            a,b=1,i\n",
    "            while favorite[b]!=i:\n",
    "                a+=1\n",
    "                deg[b]=0\n",
    "                b=favorite[b]\n",
    "            deg[b]=0\n",
    "            if a>2:\n",
    "                res=max(res,a)\n",
    "            else:\n",
    "                im.append(i)\n",
    "        def bfs(x):\n",
    "            k=0\n",
    "            que=deque()\n",
    "            que.append(x)\n",
    "            while que:\n",
    "                k+=1\n",
    "                for i in range(len(que)):\n",
    "                    u=que.popleft()\n",
    "                    for j in tree[u]:\n",
    "                        que.append(j)\n",
    "            return k\n",
    "        summ=0\n",
    "        for i in im:\n",
    "            summ=summ+bfs(i)+bfs(favorite[i])\n",
    "        return max(summ,res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        nodesout=[0]*len(favorite)\n",
    "        canuse=set(i for i in range(len(favorite)))\n",
    "        for i in range(len(favorite)):\n",
    "            nodesout[favorite[i]]+=1\n",
    "        q=[]\n",
    "        for i in range(len(nodesout)):\n",
    "            if nodesout[i]==0:\n",
    "                q.append(i)\n",
    "        dp=[1]*len(favorite)\n",
    "        while q:\n",
    "            node=q.pop(0)\n",
    "            canuse.remove(node)\n",
    "            dp[favorite[node]]=max(dp[favorite[node]],dp[node]+1)\n",
    "            nodesout[favorite[node]]-=1\n",
    "            if nodesout[favorite[node]]==0:\n",
    "                q.append(favorite[node])\n",
    "        res=0\n",
    "        tpmax=0\n",
    "        while canuse:\n",
    "            start=canuse.pop()\n",
    "            next=favorite[start]\n",
    "            if start==favorite[next]:\n",
    "                tpmax=tpmax+dp[start]+dp[next]\n",
    "                res=max(res,tpmax)\n",
    "                canuse.remove(next)\n",
    "            else:\n",
    "                loop=1\n",
    "                while start!=favorite[next]:\n",
    "                    canuse.remove(next)\n",
    "                    next=favorite[next]\n",
    "                    loop+=1\n",
    "                res=max(res,loop+1)\n",
    "                canuse.remove(next)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n = len(favorite)\n",
    "        res = Counter()\n",
    "        for i,x in enumerate(favorite):\n",
    "            res[x] += 1\n",
    "\n",
    "        # 吭哧吭哧 找基环\n",
    "        vis = [False] * n  # 找环 由于重复访问过的节点不会出现其他的环 不必继续找这些\n",
    "        s = deque([i for i in range(n) if res[i]==0])\n",
    "        f = [1] * (n)\n",
    "        while s:\n",
    "            c = s.popleft()\n",
    "            vis[c] = True\n",
    "            v = favorite[c]\n",
    "            f[v] = max(f[v], f[c]+1)\n",
    "            res[v] -= 1\n",
    "            if res[v] == 0: s.append(v)            \n",
    "\n",
    "        ans = total = 0\n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                det = favorite[i]\n",
    "                if favorite[det] == i:\n",
    "                    total += f[i] + f[det]\n",
    "                    vis[i] = vis[det] = True\n",
    "                else:\n",
    "                    u = favorite[i]\n",
    "                    cnt = 1\n",
    "                    while u != i:\n",
    "                        cnt += 1\n",
    "                        u = favorite[u]\n",
    "                        vis[u] = True\n",
    "                    vis[u] = True\n",
    "                    ans = max(ans, cnt)\n",
    "        return max(ans, total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        seen = [False]  * len(favorite)\n",
    "        ans = 0\n",
    "        for i, f in enumerate(favorite):\n",
    "            if not seen[i]:\n",
    "                length = 1\n",
    "                seen[i] = True\n",
    "                distance = {i: 0}\n",
    "                while not seen[f]:\n",
    "                    distance[f] = length\n",
    "                    length += 1\n",
    "                    seen[f] = True\n",
    "                    f = favorite[f]\n",
    "                if f in distance:\n",
    "                    ans = max(ans, length - distance[f])\n",
    "        n = len(favorite)\n",
    "        degree = [0] * n\n",
    "        for i, f in enumerate(favorite):\n",
    "            degree[f] += 1\n",
    "        nodes = set()\n",
    "        for i in range(n):\n",
    "            if i not in nodes and favorite[favorite[i]] == i:\n",
    "                nodes.add(i)\n",
    "                nodes.add(favorite[i])\n",
    "        distance = [1] * n\n",
    "        dq = deque()\n",
    "        for i, d in enumerate(degree):\n",
    "            if d == 0:\n",
    "                dq.append(i)\n",
    "        while dq:\n",
    "            u = dq.popleft()\n",
    "            v = favorite[u]\n",
    "            distance[v] = max(distance[v], distance[u] + 1)\n",
    "            degree[v] -= 1\n",
    "            if degree[v] == 0 and v not in nodes:\n",
    "                dq.append(v)\n",
    "        return max(ans, sum(distance[i] for i in nodes))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n = len(favorite)\n",
    "        degrees = [0]*n\n",
    "        for i in range(n):\n",
    "            degrees[favorite[i]] += 1\n",
    "\n",
    "        f = [0]*n  # 代表最大路径长度。\n",
    "        edge = {}\n",
    "        for i in range(n):\n",
    "            edge[i] = favorite[i]\n",
    "\n",
    "        degree0 = []\n",
    "        for i in range(n):\n",
    "            if degrees[i] == 0:\n",
    "                degree0.append(i)\n",
    "\n",
    "        while degree0:\n",
    "            new_d0 = []\n",
    "            for t in degree0:\n",
    "                degrees[edge[t]] -= 1\n",
    "                if degrees[edge[t]] == 0:\n",
    "                    new_d0.append(edge[t])\n",
    "                f[edge[t]] = max(f[edge[t]], f[t]+1)\n",
    "            degree0 = new_d0\n",
    "\n",
    "        vis = [0]*n\n",
    "        ans2 = []\n",
    "        ansmore = 0\n",
    "        for i in range(n):\n",
    "            if not vis[i] and degrees[i]:\n",
    "                vis[i] = 1\n",
    "                l = 1\n",
    "                while not vis[edge[i]]:\n",
    "                    i = edge[i]\n",
    "                    l += 1\n",
    "                    vis[i] = 1\n",
    "                if l == 2:\n",
    "                    ans2.append(f[i]+f[edge[i]]+2)\n",
    "                else:\n",
    "                    ansmore = max(ansmore, l)\n",
    "\n",
    "        return max(sum(ans2), ansmore)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n=len(favorite)\n",
    "        # print(list(enumerate(favorite)))\n",
    "        degd=Counter(favorite)\n",
    "        leafs=[k for k in range(n) if degd[k]==0]\n",
    "        # print(leafs)\n",
    "        # if len(leafs)==0:\n",
    "        #     return n\n",
    "        depth = [0]*n\n",
    "        classes = [-2]*n\n",
    "        duel_circle = {}\n",
    "        maxi_circle = 0\n",
    "        duel_cnt = 0\n",
    "        \n",
    "        def find_conn(node):\n",
    "            nonlocal maxi_circle,duel_cnt\n",
    "            this_conn=[]\n",
    "            this_conn_set=set()\n",
    "            while True:\n",
    "                if classes[node]>=0:\n",
    "                    case = 1\n",
    "                    break\n",
    "                elif node in this_conn_set:\n",
    "                    if node == favorite[favorite[node]]:\n",
    "                        classes[node] = node\n",
    "                        classes[favorite[node]] = favorite[node]\n",
    "                        duel_circle[node] = 0\n",
    "                        duel_circle[favorite[node]] = 0\n",
    "                        duel_cnt +=1\n",
    "                        case = 2 \n",
    "                    else:\n",
    "                        case = 3\n",
    "                    break\n",
    "                elif classes[node]==-1:\n",
    "                    case = 4\n",
    "                    break\n",
    "                else:\n",
    "                    this_conn.append(node)\n",
    "                    this_conn_set.add(node)\n",
    "                node = favorite[node]\n",
    "            # print(\"??\",node, case, this_conn)\n",
    "            if case==1 or case==2:\n",
    "                curcls = classes[node]\n",
    "                i = len(this_conn)-1 if case == 1 else len(this_conn)-3\n",
    "                cur = node\n",
    "                while i>=0:\n",
    "                    cur = this_conn[i]\n",
    "                    classes[cur]=curcls\n",
    "                    depth[cur]=depth[favorite[cur]]+1\n",
    "                    i-=1\n",
    "                duel_circle[classes[cur]] = max(depth[cur], duel_circle[classes[cur]])\n",
    "            if case == 3 or case == 4:\n",
    "                i = len(this_conn)-1\n",
    "                while i>=0:\n",
    "                    cur = this_conn[i]\n",
    "                    classes[cur]=-1\n",
    "                    if cur==node:\n",
    "                        maxi_circle = max(maxi_circle, len(this_conn)-i)\n",
    "                    i-=1\n",
    "            \n",
    "                    \n",
    "        for node in leafs:\n",
    "            find_conn(node)\n",
    "            # print(node,maxi_circle)\n",
    "            # print(depth)\n",
    "            # print(classes)\n",
    "            # print(duel_circle)\n",
    "        # maxi_duel = 0\n",
    "        # for k in duel_circle:\n",
    "        #     maxi_duel = max(2+duel_circle[k]+duel_circle[favorite[k]], maxi_duel)\n",
    "\n",
    "        for node in range(n):\n",
    "            if classes[node]==-2:\n",
    "                find_conn(node)\n",
    "                # print(node,maxi_circle)\n",
    "\n",
    "        return max(maxi_circle, sum(duel_circle.values())+duel_cnt*2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n = len(favorite)  # 获取收到的邀请数量\n",
    "\n",
    "        # 初始化 in_degree 和 max_length 字典，分别用于记录每个节点的入度情况和最长链\n",
    "        in_degree, max_length = defaultdict(int), defaultdict(int)\n",
    "        for x in favorite:\n",
    "            in_degree[x] += 1  # 统计每个节点的入度情况\n",
    "\n",
    "        d = deque(i for i in range(n) if in_degree[i] == 0)  # 创建一个双端队列\n",
    "\n",
    "        # 拓扑排序：求基环外的最长链\n",
    "        while d:\n",
    "            cur = d.popleft()  # 从队列中取出一个节点\n",
    "            ne = favorite[cur]  # 找到当前节点的下一个节点\n",
    "            max_length[ne] = max(max_length[ne], max_length[cur] + 1)  # 更新最长链\n",
    "            in_degree[ne] -= 1  # 更新下一个节点的入度\n",
    "            if in_degree[ne] == 0:\n",
    "                d.append(ne)  # 如果下一个节点的入度为0，将其加入队列\n",
    "\n",
    "        # 圆桌最多放置一个大于 2 的环（ans1 统计最大值）\n",
    "        # 圆桌可放置多个等于 2 的环（ans2 累加该长度）\n",
    "        ans1, ans2 = 0, 0  # 初始化两个变量，用于统计结果\n",
    "\n",
    "        for i in range(n):\n",
    "            if in_degree[i] == 0:\n",
    "                continue  # 如果当前节点的入度为0，跳过此次循环\n",
    "\n",
    "            j, cur = favorite[i], 1\n",
    "            while j != i:\n",
    "                in_degree[j] = 0  # 一个环只需被处理一次，将环中其他节点的入度置0\n",
    "                j = favorite[j]  # 找到环中的下一个节点\n",
    "                cur += 1  # 增加当前环的长度\n",
    "\n",
    "            if cur == 2:\n",
    "                ans2 += 2 + max_length[i] + max_length[favorite[i]]\n",
    "            else:\n",
    "                ans1 = max(ans1, cur)  # 更新结果 ans1 为最大环的长度\n",
    "\n",
    "        # 返回计算得到的结果中的最大值\n",
    "        return max(ans1, ans2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        self.memory = [False] * len(favorite)\n",
    "        self.inEdges = [[] for _ in range(len(favorite))]\n",
    "        ans1, ans2 = 0, 0\n",
    "        for i in range(len(favorite)):\n",
    "            self.inEdges[favorite[i]].append(i)\n",
    "        for i in range(len(favorite)):\n",
    "            if not self.memory[i]:\n",
    "                value, flag = self.findMaxLength(favorite, i)\n",
    "                if flag:\n",
    "                    ans2 += value\n",
    "                else:\n",
    "                    ans1 = max(ans1, value)\n",
    "        return max(ans1, ans2)\n",
    "\n",
    "\n",
    "    def findMaxLength(self, favorite, current):\n",
    "        record = []\n",
    "        while not self.memory[current]:\n",
    "            self.memory[current] = True\n",
    "            record.append(current)\n",
    "            current = favorite[current]\n",
    "        count = 1\n",
    "        i = len(record) - 1\n",
    "        while record[i] != current:\n",
    "            count += 1\n",
    "            i -= 1\n",
    "        if count > 2:\n",
    "            self.bfs2(record)\n",
    "            return count, False\n",
    "        memory = set()\n",
    "        memory.add(record[-1])\n",
    "        memory.add(record[-2])\n",
    "        ans1, ans2 = self.bfs1(record[-1], memory), self.bfs1(record[-2], memory)\n",
    "        return max(ans1 + ans2, 2), True\n",
    "\n",
    "\n",
    "    def bfs1(self, current, memory):\n",
    "        q = deque()\n",
    "        q.append((current, 1))\n",
    "        ans = 1\n",
    "        while q:\n",
    "            top = q.popleft()\n",
    "            for node in self.inEdges[top[0]]:\n",
    "                if node not in memory:\n",
    "                    memory.add(node)\n",
    "                    self.memory[node] = True\n",
    "                    q.append((node, top[1] + 1))\n",
    "                    ans = max(ans, top[1] + 1)\n",
    "        return ans\n",
    "\n",
    "    def bfs2(self, record):\n",
    "        q = deque()\n",
    "        for node in record:\n",
    "            q.append(node)\n",
    "        while q:\n",
    "            top = q.popleft()\n",
    "            for node in self.inEdges[top]:\n",
    "                if not self.memory[node]:\n",
    "                    self.memory[node] = True\n",
    "                    q.append(node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def get_max_cycle_length(self, favorite: List[int]) -> int:\n",
    "        person_cnt = len(favorite)\n",
    "        max_cycle_length = 0\n",
    "\n",
    "        seen = set()\n",
    "\n",
    "        # for each person\n",
    "        for i in range(person_cnt):\n",
    "            # i - person i\n",
    "\n",
    "            # if person not part of any chain (chain with cycle)\n",
    "            if i in seen:\n",
    "                continue\n",
    "            \n",
    "            # begin of chain (chain with cycle)\n",
    "            begin_person = i\n",
    "\n",
    "            # visited nodes inside of chain (chain with cycle)\n",
    "            cur_visited = set()\n",
    "\n",
    "            # cur_person\n",
    "            cur_person = i\n",
    "\n",
    "            # try to build chain with cycle\n",
    "            while cur_person not in seen:\n",
    "                seen.add(cur_person)\n",
    "                cur_visited.add(cur_person)\n",
    "                cur_person = favorite[cur_person]\n",
    "            \n",
    "            # if cycle exists\n",
    "            if cur_person in cur_visited:\n",
    "                # length of chain with cycle\n",
    "                visited_person_cnt = len(cur_visited)\n",
    "\n",
    "                # try to find length of cycle\n",
    "                while begin_person != cur_person:\n",
    "                    visited_person_cnt -= 1\n",
    "                    begin_person = favorite[begin_person]\n",
    "            \n",
    "                max_cycle_length = max(max_cycle_length, visited_person_cnt)\n",
    "        \n",
    "        return max_cycle_length\n",
    "    \n",
    "    def get_max_chain_without_cycle_length(self, favorite: List[int]) -> int:\n",
    "        person_cnt = len(favorite)\n",
    "        max_chain_len = 0\n",
    "\n",
    "        # find mutal-favorite (a <-> b) pairs\n",
    "        pairs = []\n",
    "        visited = set()\n",
    "\n",
    "        for i in range(person_cnt):\n",
    "            if i not in visited and favorite[favorite[i]] == i:\n",
    "                pairs.append((i, favorite[i]))\n",
    "                visited.add(i)\n",
    "                visited.add(favorite[i])\n",
    "\n",
    "        # build deps list, list that consits from deps from i (a -> b and c -> b, we shoul build such list [a,c] for b)\n",
    "        deps = collections.defaultdict(list)\n",
    "        for i in range(person_cnt):\n",
    "            deps[favorite[i]].append(i)\n",
    "\n",
    "        for src, dst in pairs:\n",
    "            # max chain length to src\n",
    "            max_dist_to_src = 0\n",
    "            \n",
    "            q = collections.deque()\n",
    "            for dep in deps[src]:\n",
    "                if dep != dst: q.append((dep, 1)) # dependent node and dist to dependent node\n",
    "            \n",
    "            while q:\n",
    "                cur_dependency, dist = q.popleft()\n",
    "                max_dist_to_src = max(max_dist_to_src, dist)\n",
    "                for next_dep in deps[cur_dependency]:\n",
    "                    q.append((next_dep, dist + 1))\n",
    "            \n",
    "            max_dist_to_dst = 0\n",
    "            q = collections.deque()\n",
    "            for dep in deps[dst]:\n",
    "                if dep != src: q.append((dep, 1))\n",
    "            \n",
    "            while q:\n",
    "                cur_dependency, dist = q.popleft()\n",
    "                max_dist_to_dst = max(max_dist_to_dst, dist)\n",
    "                for next_dep in deps[cur_dependency]:\n",
    "                    q.append((next_dep, dist + 1)) \n",
    "\n",
    "            max_chain_len += 2 + max_dist_to_src + max_dist_to_dst\n",
    "\n",
    "        return max_chain_len\n",
    "\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        return max(self.get_max_cycle_length(favorite), self.get_max_chain_without_cycle_length(favorite))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n = len(favorite)\n",
    "        inn = [0] * n \n",
    "        out = [[] for _ in range(n)]\n",
    "        myset = set([i for i in range(n)])\n",
    "        for i,x in enumerate(favorite):\n",
    "            out[x].append(i)\n",
    "            inn[x]+=1\n",
    "        \n",
    "        que = []\n",
    "        for i in range(n):\n",
    "            if inn[i]==0:\n",
    "                que.append(i)\n",
    "        \n",
    "        deep =[0] * n\n",
    "        h = 0\n",
    "        while que:\n",
    "            curLen = len(que)\n",
    "            h+=1\n",
    "            for _ in range(curLen):\n",
    "                i = que.pop(0)\n",
    "                myset.remove(i)\n",
    "                deep[favorite[i]] = max(deep[favorite[i]],h)\n",
    "                inn[favorite[i]]-=1\n",
    "                if inn[favorite[i]] == 0:\n",
    "                    que.append(favorite[i])\n",
    "        \n",
    "        two = 0\n",
    "        more = 0\n",
    "        while len(myset)!=0:\n",
    "            i = myset.pop()\n",
    "            if inn[i]!=0:\n",
    "                inn[i] = 0\n",
    "                next = favorite[i]\n",
    "                cnt = 1\n",
    "                while next!=i:\n",
    "                    myset.remove(next)\n",
    "                    inn[next] = 0\n",
    "                    cnt+=1\n",
    "                    next = favorite[next]\n",
    "\n",
    "                if cnt>2:\n",
    "                    more = max(more,cnt)\n",
    "                else:\n",
    "                    two += 2 + deep[i]+deep[favorite[i]]\n",
    "        \n",
    "        return max(two,more)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n = len(favorite)\n",
    "        in_degree = [0] * n\n",
    "        edges = defaultdict(list)\n",
    "        for i, p in enumerate(favorite):\n",
    "            in_degree[p] += 1\n",
    "            edges[p].append(i)\n",
    "\n",
    "        zeros = []\n",
    "        for i, v in enumerate(in_degree):\n",
    "            if v == 0:\n",
    "                zeros.append(i)\n",
    "\n",
    "        paths = [0] * n\n",
    "        #dis = 1\n",
    "        while zeros:\n",
    "            nxt = []\n",
    "            for i in zeros:\n",
    "                in_degree[favorite[i]] -= 1\n",
    "                paths[favorite[i]] = max(paths[favorite[i]], paths[i] + 1)\n",
    "                if in_degree[favorite[i]] == 0:\n",
    "                    nxt.append(favorite[i])\n",
    "            zeros = nxt\n",
    "        \n",
    "        def getPath(cur):\n",
    "            path = []\n",
    "            while vis[cur] == 0:\n",
    "                path.append(cur)\n",
    "                vis[cur] = 1\n",
    "                cur = favorite[cur]\n",
    "            return path\n",
    "\n",
    "        def getLongestPath(cur):\n",
    "            return paths[cur]\n",
    "\n",
    "        vis = [0] * n\n",
    "        cycles = []\n",
    "        ans = 0\n",
    "        #print(in_degree)\n",
    "        #paths = list(in_degree)\n",
    "        #print(\"p\", paths)\n",
    "        c = 0\n",
    "        for i in range(n):\n",
    "            if vis[i] == 0 and in_degree[i] == 1:\n",
    "                path = getPath(i)\n",
    "                # cycles.append(path)\n",
    "                ans = max(ans, len(path))\n",
    "                if len(path) == 2:\n",
    "                    # find endpoint with longest paths\n",
    "                    x, y = path[0], path[1]\n",
    "                    a = getLongestPath(x)\n",
    "                    b = getLongestPath(y)\n",
    "                    c += a + b + 2\n",
    "        ans = max(ans, c)\n",
    "        return ans\n",
    "                \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fp(self, i, favorite):\n",
    "        global l, r1, r2\n",
    "        p = [i]\n",
    "        s = set([i])\n",
    "        j = favorite[i]\n",
    "        while j not in s and j not in l:\n",
    "            p.append(j)\n",
    "            s.add(j)\n",
    "            j = favorite[j]\n",
    "        if j in l:\n",
    "            if l[j][0] == 1:\n",
    "                p.append(j)\n",
    "                c = l[j][1]\n",
    "                for k in range(len(p)-2,-1,-1):\n",
    "                    l[p[k]] = [1, c, l[p[k+1]][2]+1]\n",
    "                    r1[c] = max([r1[c], l[p[k]][2]])\n",
    "            else:\n",
    "                for kk in range(len(p)):\n",
    "                    l[p[kk]] = [2, 0, 0]\n",
    "            return 0\n",
    "        elif j==p[-2]:\n",
    "            l[p[-1]] = [1, p[-1], 1]\n",
    "            l[p[-2]] = [1, p[-2], 1]\n",
    "            r1[p[-1]] = 1\n",
    "            r1[p[-2]] = 1\n",
    "            for k in range(len(p)-3,-1,-1):\n",
    "                l[p[k]] = [1, j, l[p[k+1]][2]+1]\n",
    "                r1[j] = max([r1[j], l[p[k]][2]])\n",
    "            return 1\n",
    "        else:\n",
    "            tmp = 1\n",
    "            for k in range(len(p)-1,-1,-1):\n",
    "                if p[k] == j:\n",
    "                    for kk in range(k,len(p)):\n",
    "                        l[p[kk]] = [2, 0, tmp]\n",
    "                    for kk in range(k):\n",
    "                        l[p[kk]] = [2, 0, 0]\n",
    "                    break\n",
    "                tmp += 1\n",
    "            r2 = max([r2, tmp])\n",
    "            return 2\n",
    "\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        global l, r1, r2\n",
    "        l = {}\n",
    "        r1 = {}\n",
    "        r2 = 0\n",
    "        n = len(favorite)\n",
    "        for i in range(n):\n",
    "            if i in l:\n",
    "                continue\n",
    "            self.fp(i, favorite)\n",
    "        t = 0\n",
    "        for k in r1:\n",
    "            t += r1[k]\n",
    "        return max([t, r2])\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        #此处寻找最大舔狗环\n",
    "        ans = 0\n",
    "        mark = [True for i in range(len(favorite))]\n",
    "        for i in range(len(favorite)):\n",
    "            if mark[i]:\n",
    "                mark_new = set()\n",
    "                road = []\n",
    "                dfs = [i]\n",
    "                while dfs:\n",
    "                    tmp = dfs.pop(0)\n",
    "                    if mark[tmp] and tmp not in mark_new:\n",
    "                        road.append(tmp)\n",
    "                        dfs.append(favorite[tmp])\n",
    "                        mark_new.add(tmp)\n",
    "                        mark[tmp] = False\n",
    "                    elif tmp in mark_new:\n",
    "                        for j in range(len(road)):\n",
    "                            if road[j] == tmp:\n",
    "                                ans = max(ans,len(road)-j)\n",
    "                    elif not mark[tmp]:\n",
    "                        break\n",
    "\n",
    "        #此处寻找所有舔狗集团\n",
    "        mark2 = [0 for i in range(len(favorite))]\n",
    "        #Mark2[i] = 互舔女神i的舔狗链长度\n",
    "        dic = defaultdict(list)\n",
    "        for i in range(len(favorite)):\n",
    "            dic[favorite[i]].append(i)\n",
    "        def tree(n):\n",
    "            if len(dic[n]) == 1:\n",
    "                return 1\n",
    "            stack = [(n,1)]\n",
    "            ma = 0\n",
    "            while stack:\n",
    "                tmp,cnt = stack.pop()\n",
    "                ma = max(ma,cnt)\n",
    "                for i in dic[tmp]:\n",
    "                    if tmp != favorite[n]:\n",
    "                        stack.append((i,cnt+1))\n",
    "            return ma\n",
    "\n",
    "                    \n",
    "        for i in range(len(favorite)):\n",
    "            if i == favorite[favorite[i]] and mark2[i] == 0:\n",
    "                mark2[i] = tree(i)\n",
    "                mark2[favorite[i]] = tree(favorite[i])\n",
    "        return max(ans,sum(mark2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        l = len(favorite)\n",
    "        p_map = {}\n",
    "        for i,x in enumerate(favorite):\n",
    "            if x not in p_map:p_map[x]=[]\n",
    "            p_map[x].append(i)\n",
    "        visited = [0] * l \n",
    "        res = 0\n",
    "\n",
    "        def bfs(node,p_map,exclude):\n",
    "            res = 0\n",
    "            group = [node]\n",
    "            while group:\n",
    "                res += 1\n",
    "                tmp = []\n",
    "                for g in group:\n",
    "                    visited[g]=1\n",
    "                    if g in p_map:\n",
    "                        for gg in p_map[g]:\n",
    "                            if visited[gg]==1 or gg == exclude:continue\n",
    "                            tmp.append(gg)\n",
    "                group = tmp\n",
    "            return res\n",
    "        base = 0\n",
    "        for i in range(l):\n",
    "            if visited[i]==1:continue\n",
    "            if favorite[favorite[i]]==i: \n",
    "                circle = bfs(i,p_map,favorite[i]) + bfs(favorite[i],p_map,i)\n",
    "                res = max(res,circle)\n",
    "                base += circle\n",
    "        circle_res = res\n",
    "        for i in range(l):\n",
    "            if visited[i]==1:continue\n",
    "            circle = 0\n",
    "            node = i\n",
    "            step = 0\n",
    "            seq_map = {}\n",
    "            while visited[node]!=1:\n",
    "                visited[node]=1\n",
    "                seq_map[node]= step\n",
    "                step += 1\n",
    "                node = favorite[node]\n",
    "            if node in seq_map:\n",
    "                circle = step-seq_map[node]\n",
    "            res = max(res,circle)\n",
    "        return max(res,base) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        ans = 0\n",
    "        in_use = [False]*len(favorite)\n",
    "        nei, adj = [], defaultdict(list)\n",
    "        for i in range(len(favorite)):\n",
    "            adj[favorite[i]].append(i)\n",
    "            if in_use[i]: continue\n",
    "            j = favorite[i]\n",
    "            if favorite[j] == i:\n",
    "                nei.append((i, j))\n",
    "                in_use[i] = in_use[j] = True\n",
    "        vis = [False]*len(favorite)\n",
    "        for ps in nei:\n",
    "            if vis[ps[0]]: continue\n",
    "            cur = 2\n",
    "            vis[ps[0]] = vis[ps[1]] = True\n",
    "            for i in ps:\n",
    "                t = 0\n",
    "                q, tmp = deque([i]), []\n",
    "                while q:\n",
    "                    j = q.popleft()\n",
    "                    for k in adj[j]:\n",
    "                        if not vis[k]:\n",
    "                            tmp.append(k)\n",
    "                            vis[k] = True\n",
    "                    if not q:\n",
    "                        q = deque(tmp)\n",
    "                        if tmp:\n",
    "                            t += 1\n",
    "                        tmp = []\n",
    "                cur += t\n",
    "            ans += cur\n",
    "        for i in range(len(favorite)):\n",
    "            if not vis[i]:\n",
    "                rec = dict()\n",
    "                j, k, = i, 0\n",
    "                while not vis[j]:\n",
    "                    vis[j] = True\n",
    "                    rec[j] = k\n",
    "                    k += 1\n",
    "                    j = favorite[j]\n",
    "                if rec.get(j, None) is not None:\n",
    "                    ans = max(ans, k-rec[j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        \n",
    "        # 如果a像b,要向后构造边(b -> a),使以下BFS更容易\n",
    "        invG = defaultdict(list)\n",
    "        for idx, fav in enumerate(favorite):\n",
    "            invG[fav].append(idx)\n",
    "        \n",
    "        # 求2-cycle扩展路径的函数\n",
    "        def bfs(start, seen):\n",
    "            q = deque([(start, 0)])\n",
    "            ans = 0 \n",
    "            while q:\n",
    "                pos, dist = q.popleft()\n",
    "                for neib in invG[pos]:\n",
    "                    if neib in seen:\n",
    "                        continue\n",
    "                    seen.add(neib)\n",
    "                    q.append((neib, dist+1))\n",
    "                    ans = max(ans, dist + 1)\n",
    "            return ans\n",
    "        \n",
    "        \n",
    "        N = len(favorite)\n",
    "        \n",
    "        # 由单个大循环和所有2-cycles导出的解\n",
    "        ans_large_cycle, ans_2_cycles = 0, 0 \n",
    "        \n",
    "        # 找到所有cycles\n",
    "        for i in range(N): \n",
    "            if favorite[i] != -1:  # 以前没有探索过，在这里做一个DFS\n",
    "                dist = {i: 0}  # 记录探索的顺序\n",
    "                while favorite[i] != -1:\n",
    "                    nxt = favorite[i]\n",
    "                    favorite[i] = -1\n",
    "                    if nxt in dist:  # 识别cycle\n",
    "                        cycle_len = len(dist) - dist[nxt]  # the real cycle length\n",
    "                        \n",
    "                        # 更新从单个大循环导出的解决方案\n",
    "                        ans_large_cycle = max(ans_large_cycle, cycle_len) \n",
    "                        \n",
    "                        # 更新由2-cycle及其扩展路径导出的解\n",
    "                        if cycle_len == 2: \n",
    "                            # I是当前顶点，NXT是下一个顶点\n",
    "                            ans_2_cycles += 2 + bfs(nxt, {i, nxt}) + bfs(i, {i, nxt}) \n",
    "                    else:\n",
    "                        i = nxt\n",
    "                        dist[nxt] = len(dist)\n",
    "\n",
    "        return max(ans_large_cycle, ans_2_cycles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 找环\n",
    "# 1.大于2的环：只包括环上的人\n",
    "# 2.等于2的环：包括环上的人，以及连接在环两端，最深的链上的人\n",
    "# 圆桌上可以坐，一个大于2的环，或者，所有等于2的环\n",
    "# 比较哪个人数多\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        indegree = defaultdict(int)\n",
    "        indegree_table = defaultdict(list)\n",
    "        n = len(favorite)\n",
    "        out_circle = set()\n",
    "        in_circle = set()\n",
    "        circles = []\n",
    "        f=[1]*n\n",
    "        for i in range(n):\n",
    "            indegree[favorite[i]] += 1\n",
    "            indegree_table[favorite[i]].append(i)\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if indegree[i] == 0:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            out_circle.add(node)\n",
    "            f[favorite[node]]=max(f[favorite[node]],f[node]+1)\n",
    "            indegree[favorite[node]] -= 1\n",
    "            if indegree[favorite[node]] == 0:\n",
    "                q.append(favorite[node])\n",
    "                out_circle.add(favorite[node])\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in out_circle and i not in in_circle:\n",
    "                c = []\n",
    "                while i not in in_circle:\n",
    "                    in_circle.add(i)\n",
    "                    c.append(i)\n",
    "                    i = favorite[i]\n",
    "                circles.append(c)\n",
    "        ans1,ans2 = 0,0\n",
    "        for circle in circles:\n",
    "            if len(circle) >= 3:\n",
    "                ans1 = max(ans1, len(circle))\n",
    "            elif len(circle) == 2:\n",
    "                ans2+=(f[circle[0]]+f[circle[1]])\n",
    "        return max(ans1,ans2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "'''\n",
    "一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工。\n",
    "员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工，每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工 不会 是他自己。\n",
    "给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。\n",
    "n == favorite.length\n",
    "2 <= n <= 105\n",
    "0 <= favorite[i] <= n - 1\n",
    "favorite[i] != i\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        # 一定有环：环的大小和双向节点的路径大小\n",
    "        graph = {} # 建图\n",
    "        n = len(favorite)\n",
    "        for i in range(n):\n",
    "            graph[i] = []\n",
    "        count = [0] * n # 记录每个节点的度数\n",
    "        for i in range(n):\n",
    "            count[i] += 1\n",
    "            count[favorite[i]] += 1\n",
    "            graph[i].append(favorite[i])\n",
    "            graph[favorite[i]].append(i)\n",
    "        # 统计环的大小\n",
    "        f = {}\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            if count[i] == 1:\n",
    "                q.append([i, 1]) # 记录叶子结点\n",
    "                f[i] = 1\n",
    "        depth = 0\n",
    "        ans = 0\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            for i in range(sz):\n",
    "                x = q.pop()\n",
    "                for y in graph.get(x[0], []):\n",
    "                    count[y] -= 1\n",
    "                    if count[y] > 1:\n",
    "                        f[y] = max(x[1] + 1, f.get(y, 0))\n",
    "                    if count[y] == 1:\n",
    "                        f[y] = max(x[1] + 1, f.get(y, 0))\n",
    "                        q.append([y, f[y]])\n",
    "            depth += 1\n",
    "        count_2 =0\n",
    "        for i in range(n):\n",
    "            if count[i] > 1:\n",
    "                q1 = []\n",
    "                tmp = 1\n",
    "                q1.append(i)\n",
    "                count[i] = 0\n",
    "                l = []\n",
    "                l.append(i)\n",
    "                while q1:\n",
    "                    x = q1.pop()\n",
    "                    for y in graph.get(x, []):\n",
    "                        count[y] -= 1\n",
    "                        if count[y] == 1:\n",
    "                            l.append(y)\n",
    "                            q1.append(y)\n",
    "                            tmp += 1\n",
    "                if tmp == 2: # 如果环是2的话，是可以把连接的链加进来的\n",
    "                    sum_l = 0\n",
    "                    for z in l:\n",
    "                        max_l = 0\n",
    "                        for y in graph.get(z, []):\n",
    "                            if y in l:\n",
    "                                continue\n",
    "                            max_l = max(max_l, f.get(y, 0))\n",
    "                        sum_l += max_l\n",
    "                    ans = max(ans,tmp + sum_l + count_2)\n",
    "                    count_2 += sum_l + 2\n",
    "                else:\n",
    "                    ans = max(ans, tmp)\n",
    "        return ans\n",
    "s = Solution()\n",
    "print(s.maximumInvitations([5,13,3,14,1,1,13,13,14,10,5,13,3,14,2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n = len(favorite)\n",
    "        inv = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            inv[favorite[i]].append(i)\n",
    "        # 检测2元环\n",
    "        vis = set()\n",
    "        binaryCircles = []\n",
    "        for i in range(n):\n",
    "            if i not in vis:\n",
    "                if favorite[favorite[i]] == i:\n",
    "                    binaryCircles.append((i, favorite[i]))\n",
    "                    vis |= {i, favorite[i]}\n",
    "        max_circle = 0\n",
    "        # 检测多元环\n",
    "        for i in range(n):\n",
    "            pos = {}\n",
    "            while i not in vis:\n",
    "                vis.add(i)\n",
    "                pos[i] = len(pos)\n",
    "                i = favorite[i]\n",
    "                if i in pos:\n",
    "                    max_circle = max(max_circle, len(pos) - pos[i])\n",
    "        total = 0\n",
    "        for circle in binaryCircles:\n",
    "            for x in circle:\n",
    "                layer = [x]\n",
    "                while layer:\n",
    "                    total += 1\n",
    "                    nxt = []\n",
    "                    for node in layer:\n",
    "                        for node2 in inv[node]:\n",
    "                            if node2 not in circle:\n",
    "                                nxt.append(node2)\n",
    "                    layer = nxt\n",
    "        return max(total, max_circle)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n = len(favorite)\n",
    "        edges = defaultdict(list)\n",
    "        h = [0]*n\n",
    "        visi = set()\n",
    "        pos = defaultdict(int)\n",
    "        ans = 1\n",
    "        pair = set()\n",
    "        for i in range(n):\n",
    "            \n",
    "            if favorite[favorite[i]] == i:\n",
    "                pair.add(i)\n",
    "                pair.add(favorite[i])\n",
    "            else:\n",
    "                edges[favorite[i]].append(i)\n",
    "        visi.update(pair)\n",
    "        # print(edges)\n",
    "        for i in pair:\n",
    "            src = [i]\n",
    "            cnt = 1\n",
    "            while src:\n",
    "                visi.update(set(src))\n",
    "                nxt = []\n",
    "                cnt += 1\n",
    "                while src:\n",
    "                    j = src.pop()\n",
    "                    # for kk in edges[j]:\n",
    "                    #     if kk not in pair\n",
    "                    nxt.extend(edges[j])\n",
    "                src = nxt\n",
    "            pos[i] = cnt \n",
    "        \n",
    "        # print(pos)\n",
    "\n",
    "        def dfs(st):\n",
    "            visitmp = set()\n",
    "            cnt = 1\n",
    "            cur = st \n",
    "            visitmp.add(cur)\n",
    "            while favorite[cur] not in visitmp:\n",
    "                h[cur] = cnt\n",
    "                cnt += 1\n",
    "                visitmp.add(cur)\n",
    "                if favorite[cur] in pair:\n",
    "                    # pos[favorite[cur]] = cnt+1\n",
    "                    return cnt+1\n",
    "                else:\n",
    "                    cur = favorite[cur]\n",
    "            visi.update(visitmp)\n",
    "            return cnt - h[favorite[cur]] + 1\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in visi:\n",
    "                tmp = dfs(i)\n",
    "                # print(tmp,visi)\n",
    "                if tmp > ans :\n",
    "                    ans = tmp \n",
    "        # print(pos,pair)\n",
    "        pairkey = 0\n",
    "        # newvisi = {}\n",
    "        for i in pos:\n",
    "            # if i not in newvisi:\n",
    "            #     newvisi.add(i)\n",
    "            #     if favorite[i] in pos:\n",
    "            #         pairkey += pos[i] + pos[favorite[i]] - 4\n",
    "            #         newvisi.add(favorite[i])\n",
    "            #     else:\n",
    "            #         pairkey += pos[i] - 2\n",
    "            pairkey+=  pos[i]\n",
    "        pairkey += len(pair) - len(pos)*2\n",
    "        if ans < pairkey:\n",
    "            ans = pairkey\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        nin, already, cof, res = [set() for _ in range(len(favorite))], set(), [], 0\n",
    "        for i in range(len(favorite)):\n",
    "            if favorite[favorite[i]] == i:\n",
    "                cof.append(i)\n",
    "            else:\n",
    "                nin[favorite[i]].add(i)\n",
    "        for x in cof:\n",
    "            depth, queue = 0, [x]\n",
    "            while queue:\n",
    "                queueNext = []\n",
    "                for y in queue:\n",
    "                    already.add(y)\n",
    "                    for z in nin[y]:\n",
    "                        queueNext.append(z)\n",
    "                queue = queueNext[:]\n",
    "                depth += 1\n",
    "            res += depth\n",
    "        for i in range(len(favorite)):\n",
    "            if i not in already:\n",
    "                already.add(i)\n",
    "                dic, pres = {i: 0}, favorite[i]\n",
    "                while pres not in already:\n",
    "                    already.add(pres)\n",
    "                    dic[pres] = len(dic)\n",
    "                    pres = favorite[pres]\n",
    "                if pres in dic:\n",
    "                    res = max(res, len(dic) - dic[pres])\n",
    "                    print(dic)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        ans = 1\n",
    "        pair_cnt = 0\n",
    "        in_degree = defaultdict(set)\n",
    "        for i in range(len(favorite)):\n",
    "            in_degree[favorite[i]].add(i)\n",
    "        for i in range(len(favorite)):\n",
    "            if favorite[i] == -1:\n",
    "                continue\n",
    "            idx = favorite[i]\n",
    "            favorite[i] = -1\n",
    "            order = dict()\n",
    "            cnt = 0\n",
    "            order[i] = cnt\n",
    "            while favorite[idx] != -1:\n",
    "                cnt += 1\n",
    "                tmp = idx\n",
    "                order[idx] = cnt\n",
    "                idx = favorite[idx]\n",
    "                favorite[tmp] = -1\n",
    "            if tmp not in order or idx not in order:\n",
    "                continue\n",
    "            cnt = order[tmp] - order[idx] + 1\n",
    "            if cnt == 2:\n",
    "                a, b = idx, tmp\n",
    "                in_degree[a].discard(b)\n",
    "                in_degree[b].discard(a)\n",
    "                # a list\n",
    "                q = [a]\n",
    "                a_cnt = -1\n",
    "                while q:\n",
    "                    qlen = len(q)\n",
    "                    a_cnt += 1\n",
    "                    for j in range(qlen):\n",
    "                        node = q.pop(0)\n",
    "                        q += in_degree[node]\n",
    "\n",
    "                # b list\n",
    "                q = [b]\n",
    "                b_cnt = -1\n",
    "                while q:\n",
    "                    qlen = len(q)\n",
    "                    b_cnt += 1\n",
    "                    for j in range(qlen):\n",
    "                        node = q.pop(0)\n",
    "                        q += in_degree[node]\n",
    "                \n",
    "                pair_cnt += 2+a_cnt+b_cnt\n",
    "            ans = max(ans, cnt)\n",
    "        return max(ans, pair_cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        g = {}\n",
    "        used = set()\n",
    "        n = len(favorite)\n",
    "        res = 0\n",
    "        pair = []\n",
    "        for index in range(n):\n",
    "            if favorite[index] not in g:\n",
    "                g[favorite[index]] = set()\n",
    "            g[favorite[index]].add(index)\n",
    "\n",
    "            if index not in used:\n",
    "                used.add(index)\n",
    "                next = favorite[index]\n",
    "                stack = [index]\n",
    "                circle = set([index])\n",
    "                while next not in circle and next not in used:\n",
    "                    used.add(next)\n",
    "                    circle.add(next)\n",
    "                    stack.append(next)\n",
    "                    next = favorite[next]\n",
    "                \n",
    "                if next not in circle:\n",
    "                    continue\n",
    "\n",
    "                step = 0\n",
    "                while stack:\n",
    "                    now = stack.pop()\n",
    "                    step += 1\n",
    "                    if now == next:\n",
    "                        break\n",
    "\n",
    "                if step == 2:\n",
    "                    pair.append([now, favorite[now]])\n",
    "                else:\n",
    "                    res = max(res, step)\n",
    "\n",
    "        def bfs(start):\n",
    "            q = [start]\n",
    "            l = 0\n",
    "            r = 1\n",
    "            step = 0\n",
    "            while l < r:\n",
    "                step += 1\n",
    "                for now in q[l : r]:\n",
    "                    for next in g.get(now, set()):\n",
    "                        q.append(next)\n",
    "                \n",
    "                l, r = r, len(q)\n",
    "\n",
    "            return step\n",
    "\n",
    "        cnt = 0\n",
    "        for x, y in pair:\n",
    "            g[x].remove(y)\n",
    "            g[y].remove(x)\n",
    "            cnt += bfs(x) + bfs(y)\n",
    "\n",
    "        return max(res, cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        visited = {}\n",
    "        can = {}\n",
    "        n = len(favorite)\n",
    "        twins = {}\n",
    "        ans = 0\n",
    "        mapping = {idx: f for idx, f in enumerate(favorite)}\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                tmpm = {i: 0}\n",
    "                cnt = 1\n",
    "                ne = mapping[i]\n",
    "                while ne not in visited:\n",
    "                    tmpm[ne] = cnt\n",
    "                    cnt += 1\n",
    "                    ne = mapping[ne]\n",
    "                    if ne in tmpm:\n",
    "                        l = len(tmpm)\n",
    "                        cur = len(tmpm) - tmpm[ne]\n",
    "                        if cur == 2:\n",
    "                            side = 0 if ne < mapping[ne] else 1\n",
    "                            cp = (min(ne, mapping[ne]), max(ne, mapping[ne]))\n",
    "                            if cp in twins:\n",
    "                                le, ri = twins[cp]\n",
    "                                if ne < mapping[ne]:\n",
    "                                    twins[cp] = (max(le, l), ri)\n",
    "                                else:\n",
    "                                    twins[cp] = (le, max(ri, l))\n",
    "                            else:\n",
    "                                if ne < mapping[ne]:\n",
    "                                    twins[cp] = (l, 2)\n",
    "                                else:\n",
    "                                    twins[cp] = (2, l)\n",
    "                            for t, j in tmpm.items():\n",
    "                                visited[t] = l - j\n",
    "                                can[t] = (cp, side)\n",
    "                            visited[mapping[ne]] = 2\n",
    "                            can[mapping[ne]] = (cp, 1 - side)\n",
    "                        else:\n",
    "                            for t, j in tmpm.items():\n",
    "                                if j < tmpm[ne]:\n",
    "                                    visited[t] = - 1\n",
    "                                else:\n",
    "                                    visited[t] = cur\n",
    "                            ans = max(ans, cur)\n",
    "                        break\n",
    "                else:\n",
    "                    if ne not in can:\n",
    "                        for t in tmpm:\n",
    "                            visited[t] = -1\n",
    "                    else:\n",
    "                        l = len(tmpm)\n",
    "                        cp, side = can[ne]\n",
    "                        le, ri = twins[cp]\n",
    "                        if side == 0:\n",
    "                            twins[cp] = (max(le, l + visited[ne]), ri)\n",
    "                        else:\n",
    "                            twins[cp] = (le, max(ri, l + visited[ne]))\n",
    "                        for t, j in tmpm.items():\n",
    "                            visited[t] = l - j + visited[ne]\n",
    "                            can[t] = (cp, side)\n",
    "        tmp = 0\n",
    "        for cp, (le, ri) in twins.items():\n",
    "            tmp += le + ri - 2\n",
    "        return max(ans, tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        reversed_graph = collections.defaultdict(list)\n",
    "        indeg = collections.defaultdict(int)\n",
    "\n",
    "        n = len(favorite)\n",
    "        for u, v in enumerate(favorite):\n",
    "            graph[u].append(v)\n",
    "            reversed_graph[v].append(u)\n",
    "            indeg[v] += 1\n",
    "        \n",
    "        deque = collections.deque([u for u in range(n) if indeg[u]==0])\n",
    "        while deque:\n",
    "            u = deque.popleft()\n",
    "            # for v in graph[u]:\n",
    "            v = favorite[u]\n",
    "            indeg[v] -= 1\n",
    "            if indeg[v] == 0:\n",
    "                deque.append(v)\n",
    "        \n",
    "        def bfs1(root):\n",
    "            depth = 0\n",
    "            deque = collections.deque([root])\n",
    "            while deque:\n",
    "                u = deque.popleft()\n",
    "                if u in visited:\n",
    "                    return depth\n",
    "                visited.add(u)\n",
    "                deque.append(favorite[u])\n",
    "                depth += 1\n",
    "\n",
    "\n",
    "        def dfs(u, depth):\n",
    "            if u in visited:\n",
    "                return depth\n",
    "            visited.add(u)\n",
    "            return dfs(favorite[u], depth+1)\n",
    "        \n",
    "        starts = [u for u in range(n) if indeg[u]>0]\n",
    "        visited = set()\n",
    "        records = []\n",
    "        max_circle_len = 0\n",
    "        # print(starts)\n",
    "        for u in starts:\n",
    "            if u in visited:\n",
    "                continue\n",
    "            # circle_len = dfs(u, 0)\n",
    "            circle_len = bfs1(u)\n",
    "            max_circle_len = max(max_circle_len, circle_len)\n",
    "            # print(u, circle_len, visited)\n",
    "            if circle_len==2:\n",
    "                records.append((u, favorite[u]))\n",
    "\n",
    "        if len(records) == 0:\n",
    "            return max_circle_len\n",
    "        \n",
    "        def dfs2(u, step):\n",
    "            if not reversed_graph[u]:\n",
    "                return step\n",
    "            return max(dfs2(child, step+1) for child in reversed_graph[u])\n",
    "        \n",
    "        max_depth = 0\n",
    "        def dfs2(u, depth):\n",
    "            nonlocal max_depth\n",
    "            max_depth = max(max_depth, depth)\n",
    "            for v in reversed_graph[u]:\n",
    "                dfs2(v, depth+1)\n",
    "\n",
    "        def bfs2(root):\n",
    "            depth = 0\n",
    "            deque = collections.deque([root])\n",
    "            while deque:\n",
    "                depth += 1\n",
    "                for _ in range(len(deque)):\n",
    "                    u = deque.popleft()\n",
    "                    for v in reversed_graph[u]:\n",
    "                        deque.append(v)\n",
    "            return depth\n",
    "\n",
    "        # print(records)\n",
    "        # print(reversed_graph)\n",
    "        pair_path_len = 0\n",
    "        while records:\n",
    "            u, v = records.pop()\n",
    "            reversed_graph[u] = [i for i in reversed_graph[u] if i!=v]\n",
    "            reversed_graph[v] = [i for i in reversed_graph[v] if i!=u]\n",
    "            # print(reversed_graph)\n",
    "            # max_depth = 0\n",
    "            # dfs2(u,1)\n",
    "            # left = max_depth\n",
    "            # max_depth = 0\n",
    "            # dfs2(v,1)\n",
    "            # right = max_depth\n",
    "            left = bfs2(u)\n",
    "            right = bfs2(v)\n",
    "            # left = dfs2(u,0)\n",
    "            # right = dfs2(v,0)\n",
    "            # print(left, right)\n",
    "            pair_path_len += left+right\n",
    "        \n",
    "        ans = max(max_circle_len, pair_path_len)\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "         \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        # 有两种情况：\n",
    "        # 一个二元环和最多两个单相思链\n",
    "        # 一个环\n",
    "        n = len(favorite)\n",
    "        be_liked = defaultdict(set)\n",
    "        in_degree = defaultdict(int)\n",
    "        for i, c in enumerate(favorite):\n",
    "            be_liked[c].add(i)\n",
    "            in_degree[c] += 1\n",
    "\n",
    "        # 拓扑排序找到最长的单相思链\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if in_degree[i] == 0:\n",
    "                q.append(i)\n",
    "        be_liked_length = defaultdict(int)\n",
    "        deep = 1\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                a = q.popleft()\n",
    "                b = favorite[a]\n",
    "                be_liked_length[a] = deep\n",
    "                in_degree[b] -= 1\n",
    "                if in_degree[b] == 0:\n",
    "                    q.append(b)\n",
    "            deep += 1\n",
    "        \n",
    "        ans = 1\n",
    "        # 二元环时不闭合的，所以二元环可以全部放进去\n",
    "        two_circle = 0\n",
    "        # 找环\n",
    "        for i in range(n):\n",
    "            if be_liked_length[i] == 0:\n",
    "                p = favorite[i]\n",
    "                cnt = 2\n",
    "                be_liked_length[i] = be_liked_length[p] = 1\n",
    "                # 二元环\n",
    "                if favorite[p] == i:\n",
    "                    cnt_i = 0\n",
    "                    for c in be_liked[i] - {p}:\n",
    "                        cnt_i = max(cnt_i, be_liked_length[c])\n",
    "                    cnt_p = 0\n",
    "                    for c in be_liked[p] - {i}:\n",
    "                        cnt_p = max(cnt_p, be_liked_length[c])\n",
    "                    # 两边都取最长的链\n",
    "                    cnt += cnt_i + cnt_p\n",
    "                    two_circle += cnt\n",
    "                    continue\n",
    "                cnt = 1\n",
    "                # 多元环\n",
    "                while p != i:\n",
    "                    cnt += 1\n",
    "                    p = favorite[p]\n",
    "                    be_liked_length[p] = 1\n",
    "                ans = max(ans, cnt)\n",
    "        return max(ans, two_circle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        # 有两种情况：\n",
    "        # 一个二元环和最多两个单相思链\n",
    "        # 一个环\n",
    "        n = len(favorite)\n",
    "        be_liked = defaultdict(set)\n",
    "        in_degree = defaultdict(int)\n",
    "        for i, c in enumerate(favorite):\n",
    "            be_liked[c].add(i)\n",
    "            in_degree[c] += 1\n",
    "\n",
    "        # 拓扑排序找到最长的单相思链\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if in_degree[i] == 0:\n",
    "                q.append(i)\n",
    "        be_liked_length = defaultdict(int)\n",
    "        deep = 1\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                a = q.popleft()\n",
    "                b = favorite[a]\n",
    "                be_liked_length[a] = deep\n",
    "                in_degree[b] -= 1\n",
    "                if in_degree[b] == 0:\n",
    "                    q.append(b)\n",
    "            deep += 1\n",
    "        \n",
    "        ans = 1\n",
    "        # 二元环时不闭合的，所以二元环可以全部放进去\n",
    "        two_circle = 0\n",
    "        # 找环\n",
    "        for i in range(n):\n",
    "            if be_liked_length[i] == 0:\n",
    "                p = favorite[i]\n",
    "                cnt = 2\n",
    "                be_liked_length[i] = be_liked_length[p] = 1\n",
    "                # 二元环\n",
    "                if favorite[p] == i:\n",
    "                    cnt_i = 0\n",
    "                    for c in be_liked[i] - {p}:\n",
    "                        cnt_i = max(cnt_i, be_liked_length[c])\n",
    "                    cnt_p = 0\n",
    "                    for c in be_liked[p] - {i}:\n",
    "                        cnt_p = max(cnt_p, be_liked_length[c])\n",
    "                    # 两边都取最长的链\n",
    "                    cnt += cnt_i + cnt_p\n",
    "                    two_circle += cnt\n",
    "                    continue\n",
    "                cnt = 1\n",
    "                # 多元环\n",
    "                while p != i:\n",
    "                    cnt += 1\n",
    "                    p = favorite[p]\n",
    "                    be_liked_length[p] = 1\n",
    "                ans = max(ans, cnt)\n",
    "        return max(ans, two_circle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.ancestors = [i for i in range(n)]\n",
    "\n",
    "    def find(self, a):\n",
    "        if a == self.ancestors[a]:\n",
    "            return a \n",
    "        self.ancestors[a] = self.find(self.ancestors[a])\n",
    "        return self.ancestors[a]\n",
    "\n",
    "    def merge(self, a, b):\n",
    "        aa = self.find(a)\n",
    "        ba = self.find(b)\n",
    "        self.ancestors[ba] = aa\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n = len(favorite)\n",
    "        dp = [0] * n\n",
    "\n",
    "        # construct graph\n",
    "        graph = [[] for _ in range(n)]\n",
    "        indeg = [0] * n\n",
    "        for i in range(n):\n",
    "            graph[favorite[i]].append(i)\n",
    "            indeg[favorite[i]] += 1\n",
    "\n",
    "        # divide connecting components\n",
    "        uf = UnionFind(n)\n",
    "        for i in range(n):\n",
    "            uf.merge(i,favorite[i])\n",
    "        components = defaultdict(set)\n",
    "        for i in range(n):\n",
    "            components[uf.find(i)].add(i)\n",
    "\n",
    "        ans3 = 0\n",
    "        ans2 = 0\n",
    "        # for each components ...\n",
    "        for component in components.values():\n",
    "            nodes = deque([i for i in component if indeg[i] == 0])\n",
    "            while nodes:\n",
    "                cur = nodes.popleft()\n",
    "                dp[cur] = max([dp[i] for i in graph[cur]], default = 0) + 1\n",
    "                indeg[favorite[cur]] -= 1\n",
    "                if indeg[favorite[cur]] == 0:\n",
    "                    nodes.append(favorite[cur])\n",
    "\n",
    "            ring = [i for i in range(n) if i in component and indeg[i] > 0]\n",
    "            if len(ring) > 2:\n",
    "                this = len(ring)\n",
    "                ans3 = max(ans3, this)\n",
    "            else:\n",
    "                this = max([dp[i] for i in graph[ring[0]]], default = 0) + max([dp[i] for i in graph[ring[1]]], default = 0) + 2\n",
    "                ans2 += this\n",
    "                \n",
    "\n",
    "        return max(ans3, ans2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, i) -> None:\n",
    "        self.i = i\n",
    "        self.children = []\n",
    "        self.parents = []\n",
    "        self.neighbors = []\n",
    "        self.visited = False\n",
    "\n",
    "    def __hash__(self) -> int:\n",
    "        return self.i\n",
    "\n",
    "\n",
    "class Graph:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.nodes = [Node(i) for i in range(n)]\n",
    "\n",
    "    def add_directed_edge(self, i, j):\n",
    "        self.nodes[i].children.append(self.nodes[j])\n",
    "        self.nodes[j].parents.append(self.nodes[i])\n",
    "\n",
    "    def add_undirected_edge(self, i, j):\n",
    "        self.nodes[i].neighbors.append(self.nodes[j])\n",
    "        self.nodes[j].neighbors.append(self.nodes[i])\n",
    "\n",
    "    \n",
    "class Solution:\n",
    "    def trace_parent(self, node, v):\n",
    "        parents = set(p.i for p in node.parents if not v[p.i])\n",
    "        length = 0\n",
    "        \n",
    "        while parents:\n",
    "            length += 1\n",
    "            new_parents = set()\n",
    "            for pi in parents:\n",
    "                v[pi] = True\n",
    "                for pp in self.graph.nodes[pi].parents:\n",
    "                    if not v[pp.i]:\n",
    "                        new_parents.add(pp.i)\n",
    "            if not new_parents:\n",
    "                break\n",
    "            parents = new_parents\n",
    "            \n",
    "\n",
    "        return length\n",
    "\n",
    "    def maximumInvitations(self, favorite) -> int:\n",
    "        n = len(favorite)\n",
    "        self.graph = Graph(n)\n",
    "\n",
    "        for i, j in enumerate(favorite):\n",
    "            self.graph.add_directed_edge(i, j)\n",
    "\n",
    "        total_length_pattern_1 = 0\n",
    "        total_length_pattern_2 = 0\n",
    "\n",
    "        visited = [False] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            if visited[i]:\n",
    "                continue\n",
    "            \n",
    "            circle = [i]\n",
    "            cset = {i: 0}\n",
    "            # in this problem, one node has exactly one child\n",
    "            child_i = i\n",
    "            while True:\n",
    "                child_i = favorite[child_i]\n",
    "                if child_i in cset:\n",
    "                    break\n",
    "                circle.append(child_i)\n",
    "                cset[child_i] = len(circle) - 1\n",
    "\n",
    "            # print([node.i for node in circle])\n",
    "            # print(len(circle))\n",
    "            if len(circle) - cset[child_i] == 2:\n",
    "                node1, node2 = self.graph.nodes[circle[-2]], self.graph.nodes[circle[-1]]\n",
    "                visited[circle[-2]] = True\n",
    "                visited[circle[-1]] = True\n",
    "                trace1 = self.trace_parent(node1, visited)\n",
    "                trace2 = self.trace_parent(node2, visited)\n",
    "                total_length_pattern_1 += 2 + trace1 + trace2\n",
    "            else:\n",
    "                # len(circle) >= 3, since one cannot favor himself\n",
    "                for i in circle:\n",
    "                    visited[i] = True\n",
    "                total_length_pattern_2 = max(total_length_pattern_2, len(circle) - cset[child_i])\n",
    "\n",
    "        # print(total_length_pattern_1, total_length_pattern_2)\n",
    "        return max(total_length_pattern_1, total_length_pattern_2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n = len(favorite)\n",
    "\n",
    "        degree = [0]*n\n",
    "        inverse = [[] for _ in range(n)]\n",
    "        tail = [0]*n\n",
    "        for i in range(n):\n",
    "            degree[favorite[i]]+=1\n",
    "            inverse[favorite[i]].append(i)\n",
    "        \n",
    "        i = 0\n",
    "        while i<n:\n",
    "            x = i\n",
    "            while not degree[x]:\n",
    "                degree[x]-=1\n",
    "                x = favorite[x]\n",
    "                degree[x]-=1\n",
    "            i+=1\n",
    "        \n",
    "        visited = [False]*n\n",
    "        special = 0\n",
    "        res = 0\n",
    "\n",
    "        def help(i):\n",
    "            if tail[i]:\n",
    "                return tail[i]\n",
    "\n",
    "            if not inverse[i]:\n",
    "                tail[i] = 1\n",
    "                return 1\n",
    "            \n",
    "            tail[i] = max(help(j) for j in inverse[i])+1\n",
    "            return tail[i]\n",
    "\n",
    "        for i in range(n):\n",
    "            if degree[i]==-1 and tail[i]==0:\n",
    "                help(i)\n",
    "\n",
    "        for i in range(n):\n",
    "            if visited[i] or degree[i]==-1:\n",
    "                continue\n",
    "            x = i \n",
    "            length = 0\n",
    "            while not visited[x]:\n",
    "                visited[x] = True\n",
    "                x = favorite[x]\n",
    "                length+=1\n",
    "            if length==2:\n",
    "                special += 2+max(tail[j] for j in inverse[i])+max(tail[j] for j in inverse[favorite[i]])\n",
    "            else:\n",
    "                res = max(res, length)\n",
    "        return max(res, special)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        # 能做到一起的话有两种可能性, 一种是构成一个圈 另外一种是开头是两个人相互喜欢, 然后后面跟了一群喜欢的人\n",
    "        result = 0\n",
    "\n",
    "        # 首先寻找大圈, 如果把人与人之间的关系看做是一个图的话, 那么这个图的所有的元素的出度都是 1, 查找入度为0的点并且去除\n",
    "        liked_dict = defaultdict(set)\n",
    "        for like, liked in enumerate(favorite):\n",
    "            liked_dict[liked].add(like)\n",
    "        liked_dict_copy = copy.deepcopy(liked_dict)\n",
    "\n",
    "        tmp_list = [i for i in range(len(favorite)) if not liked_dict.get(i, set())]\n",
    "        # print(liked_dict)\n",
    "        # print(tmp_list)\n",
    "        while tmp_list:\n",
    "            tmp_list_2 = []\n",
    "            for i in tmp_list:\n",
    "                liked_liked = favorite[i]\n",
    "                liked_dict[liked_liked].remove(i)\n",
    "                if not liked_dict[liked_liked]:\n",
    "                    tmp_list_2.append(liked_liked)\n",
    "            tmp_list = tmp_list_2\n",
    "        other_num = set([i for i in liked_dict if liked_dict[i]])\n",
    "        tmp_set = set()\n",
    "        for i in other_num:\n",
    "            if i in tmp_set:\n",
    "                continue\n",
    "            num = 0\n",
    "            while i not in tmp_set:\n",
    "                # print(i)\n",
    "                num += 1\n",
    "                tmp_set.add(i)\n",
    "                i = favorite[i]\n",
    "            # print(\"-------\")\n",
    "            result = max(result, num)\n",
    "\n",
    "        # print(result)\n",
    "\n",
    "        # 计算两个人互相like 加上后面拖着一堆人的情况\n",
    "        pair_list = []\n",
    "        for i in range(len(favorite)):\n",
    "            j = favorite[i]\n",
    "            if favorite[j] == i and i < j:\n",
    "                pair_list.append([i, favorite[i]])\n",
    "        # print(pair_list)\n",
    "\n",
    "        result_2 = 0\n",
    "\n",
    "        for i, j in pair_list:\n",
    "            tmp = 2\n",
    "            tmp_list = []\n",
    "            for k in liked_dict_copy[i]:\n",
    "                if k != j:\n",
    "                    tmp_list.append(k)\n",
    "\n",
    "            while tmp_list:\n",
    "                tmp += 1\n",
    "                tmp_list_2 = []\n",
    "                for k in tmp_list:\n",
    "                    for l in liked_dict_copy[k]:\n",
    "                        tmp_list_2.append(l)\n",
    "                tmp_list = tmp_list_2\n",
    "\n",
    "            tmp_list = []\n",
    "            for k in liked_dict_copy[j]:\n",
    "                if k != i:\n",
    "                    tmp_list.append(k)\n",
    "            while tmp_list:\n",
    "                tmp += 1\n",
    "                tmp_list_2 = []\n",
    "                for k in tmp_list:\n",
    "                    for l in liked_dict_copy[k]:\n",
    "                        tmp_list_2.append(l)\n",
    "                tmp_list = tmp_list_2\n",
    "\n",
    "            result_2 += tmp\n",
    "        result = max(result, result_2)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n = len(favorite)\n",
    "        a = list(range(n))\n",
    "        \n",
    "        def f(i):\n",
    "            if a[i] != i:\n",
    "                a[i] = f(a[i])\n",
    "            return a[i]\n",
    "        \n",
    "        for i in range(n):\n",
    "            a[f(i)] = f(favorite[i])\n",
    "        d = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            d[f(i)].append(i)\n",
    "        m, s = 0, 0\n",
    "        \n",
    "        def f(a, i, j):\n",
    "            d = defaultdict(list)\n",
    "            for k in a:\n",
    "                d[favorite[k]].append(k)\n",
    "            d[i].remove(j)\n",
    "            d[j].remove(i)\n",
    "            \n",
    "            def f(i):\n",
    "                k, a = 0, [i]\n",
    "                while a:\n",
    "                    a = list(chain.from_iterable(d.pop(j) for j in a if j in d))\n",
    "                    k += 1\n",
    "                return k\n",
    "            \n",
    "            return f(i) + f(j)\n",
    "               \n",
    "        while d:\n",
    "            a = d.popitem()[1]\n",
    "            c, i = {}, a[0]\n",
    "            while i not in c:\n",
    "                c[i] = len(c)\n",
    "                i = favorite[i]\n",
    "            if (c := len(c) - c[i]) > 2:\n",
    "                m = max(m, c)\n",
    "                continue\n",
    "            s += f(a, i, favorite[i])\n",
    "        return max(m, s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n = len(favorite)\n",
    "        ans = 0\n",
    "        degs = [0 for _ in range(n)]\n",
    "        deps = [1 for _ in range(n)]\n",
    "        dq = deque()\n",
    "        \n",
    "        for i in range(n):\n",
    "            degs[favorite[i]] += 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            if degs[i] == 0:\n",
    "                dq.append(i)\n",
    "        \n",
    "        while len(dq) > 0:\n",
    "            #print(repr(dq))\n",
    "            cv = dq.popleft()\n",
    "            degs[favorite[cv]] -= 1\n",
    "            deps[favorite[cv]] = max(deps[favorite[cv]], deps[cv] + 1)\n",
    "            #print(repr(deps))\n",
    "            if degs[favorite[cv]] == 0:\n",
    "                dq.append(favorite[cv])\n",
    "        \n",
    "        def dfsr(i, cnt=0):\n",
    "            if degs[i] == -1:\n",
    "                return cnt\n",
    "            degs[i] = -1\n",
    "            return dfsr(favorite[i], cnt + 1)\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if degs[i] > 0:\n",
    "                rlen = dfsr(i)\n",
    "                if rlen > 2:\n",
    "                    ans = max(ans, rlen)\n",
    "                else:\n",
    "                    total += deps[i] + deps[favorite[i]]\n",
    "        \n",
    "        #print(repr(deps))\n",
    "        return max(ans, total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, g: List[int]) -> int:\n",
    "        n = len(g)\n",
    "        degree = [0]*n\n",
    "        for i in g:\n",
    "            degree[i] += 1\n",
    "        vis = [0]*n\n",
    "        lis = []\n",
    "        for i,v in enumerate(degree):\n",
    "            if v == 0:\n",
    "                lis.append([i,1])\n",
    "        q = deque(lis)\n",
    "        while q:\n",
    "            node,v = q.popleft()\n",
    "            vis[node] =-1\n",
    "            t_node = g[node]\n",
    "            degree[t_node] -=1\n",
    "            if degree[t_node] == 0:\n",
    "                v = max(vis[t_node],v)\n",
    "                vis[t_node] = 0\n",
    "                q.append([t_node,v+1])\n",
    "            else:\n",
    "                vis[t_node] = v\n",
    "        \n",
    "        ans = 0\n",
    "        ans1 = 0\n",
    "        def dfs(node):\n",
    "            \n",
    "            if degree[node] == 0:\n",
    "                return\n",
    "            res.append(vis[node])\n",
    "            vis[node] = -1\n",
    "            degree[node] -= 1\n",
    "            dfs(g[node])\n",
    "        for ind,val in enumerate(vis):\n",
    "            res = []\n",
    "            if val != -1:\n",
    "                dfs(ind)\n",
    "                if len(res) == 2:\n",
    "                    ans1+=2+sum(res)\n",
    "                else:\n",
    "                    ans = max(ans,len(res))\n",
    "\n",
    "\n",
    "        return max(ans1,ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        # 2 people circle\n",
    "        # circle love\n",
    "        n=len(favorite)\n",
    "        deg = [0]*n\n",
    "        len_map=defaultdict(int)\n",
    "        for i,v in enumerate(favorite):\n",
    "            deg[v]+=1\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            if deg[i]==0:\n",
    "                stack.append([i,1])\n",
    "        while stack:\n",
    "            pop = stack.pop()\n",
    "            deg[favorite[pop[0]]]-=1\n",
    "            if deg[favorite[pop[0]]]==0:\n",
    "                length = pop[1]\n",
    "                if favorite[pop[0]] in len_map:\n",
    "                    length = max(length,len_map[favorite[pop[0]]])\n",
    "                \n",
    "                stack.append([favorite[pop[0]],length+1])\n",
    "            else:\n",
    "                len_map[favorite[pop[0]]] = max(len_map[favorite[pop[0]]],pop[1])\n",
    "        visited = set()\n",
    "        def dfs(idx,cnt):\n",
    "            if idx in visited:\n",
    "                return cnt\n",
    "            cnt+=1\n",
    "            visited.add(idx)\n",
    "            return dfs(favorite[idx],cnt)\n",
    "        cnt1=0\n",
    "        cnt2=0\n",
    "        for i in range(n):\n",
    "            if i not in visited and deg[i]==1:\n",
    "                cnt=dfs(i,0)\n",
    "                if cnt>2:\n",
    "                    cnt1=max(cnt1,cnt)\n",
    "                if cnt==2:\n",
    "                    cnt2+=len_map[i]\n",
    "                    cnt2+=len_map[favorite[i]]\n",
    "                    cnt2+=2\n",
    "        return max(cnt1,cnt2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n = len(favorite)\n",
    "        debug = 0\n",
    "        maxone = 0\n",
    "        cirs2 = []\n",
    "        used = [0] * n\n",
    "        roots = [None] * n\n",
    "        othercirs = []\n",
    "        for i in range(n):\n",
    "            if used[i]:\n",
    "                continue\n",
    "            viewed = set()\n",
    "            now = i\n",
    "            while now not in viewed and not used[now]:\n",
    "                viewed.add(now)\n",
    "                used[now] = 1\n",
    "                now = favorite[now]\n",
    "            if now not in viewed or used[now] == -1:\n",
    "                continue\n",
    "            circle = []\n",
    "            while not circle or circle[0] != now:\n",
    "                circle.append(now)\n",
    "                used[now] = -1\n",
    "                roots[now] = [0,now]\n",
    "                now = favorite[now]\n",
    "            if len(circle) == 2:\n",
    "                cirs2.append(circle)\n",
    "            else:\n",
    "                othercirs.append(circle)\n",
    "                maxone = max(maxone,len(circle))\n",
    "            # return 0\n",
    "        if debug:\n",
    "            print(cirs2)\n",
    "            print(othercirs)\n",
    "            print(used)\n",
    "            print(maxone)\n",
    "        def _cal(i):\n",
    "            if not roots[i]:\n",
    "                dis,root = _cal(favorite[i])\n",
    "                roots[i] = [dis+1,root]\n",
    "            return roots[i]\n",
    "        maxdisarr = [0] * n\n",
    "        for i in range(n):\n",
    "            dis,root = _cal(i)\n",
    "            maxdisarr[root] = max(maxdisarr[root],dis)\n",
    "        if debug:\n",
    "            print(roots)\n",
    "            print(maxdisarr)\n",
    "        cnt = 0\n",
    "        for arr in cirs2:\n",
    "            base = 2\n",
    "            for x in arr:\n",
    "                base += maxdisarr[x]\n",
    "            cnt += base\n",
    "        return max(maxone,cnt)\n",
    "'''\n",
    "[2,2,1,2]\n",
    "[1,2,0]\n",
    "[3,0,1,4,1]\n",
    "[1,0,0,2,1,4,7,8,9,6,7,10,8]\n",
    "[1,0,3,2,5,6,7,4,9,8,11,10,11,12,10]\n",
    "[7,0,7,13,11,6,8,5,9,8,9,14,15,7,11,6]\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find_list(self, g, x, solved):\n",
    "        res = 0\n",
    "        for u in g[x]:\n",
    "            if u not in solved:\n",
    "                solved.add(u)\n",
    "                res = max(res, self.find_list(g, u, solved) + 1)\n",
    "        return res\n",
    "\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        # u->v for u like v\n",
    "        # x1->x2, x2->x1, x3->x1, x4->x1, then result is 3, if x6->x5->x2, then result is 5, \n",
    "        # if x9->x8->x7->x2, then result is 6, ...\n",
    "        # x1->x2, x2->x3, x3->x1, then result is 3, if x4->x1, then result is still 3\n",
    "        n = len(favorite)\n",
    "        solved = set()\n",
    "        res = 0  # 所有x1->x2->x3->x1都不能组合和扩展，答案是3\n",
    "        res2 = 0 # 所有x1->x2->x1及其扩展xi->...->x1,xj->...->x2都可以组合\n",
    "        # 如x1->x2->x1,x3->x4->x3，则答案是4\n",
    "\n",
    "        g = [[] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            u = favorite[i]\n",
    "            g[u].append(i)\n",
    "\n",
    "        for i in range(n):\n",
    "            u = favorite[i]\n",
    "            if favorite[u] == i and i not in solved:\n",
    "                solved.add(u)\n",
    "                solved.add(i)\n",
    "                res2 += 2 + self.find_list(g, u, solved) + self.find_list(g, i, solved)\n",
    "        \n",
    "        # print(solved, res2)\n",
    "        for i in range(n):\n",
    "            if i not in solved:\n",
    "                u = favorite[i]\n",
    "                cnt = 0\n",
    "                tmp = {i: cnt}\n",
    "                while u not in solved:\n",
    "                    cnt += 1\n",
    "                    tmp[u] = cnt \n",
    "                    solved.add(u)\n",
    "                    u = favorite[u]\n",
    "                # print(\"tmp=\",tmp, \"u=\", u)\n",
    "                if u in tmp:\n",
    "                    res = max(res, cnt + 1 - tmp[u])\n",
    "        \n",
    "        return max(res, res2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n = len(favorite)\n",
    "        edge = [[] for _ in range(n)]\n",
    "        rank = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            edge[i].append(favorite[i])\n",
    "            rank[favorite[i]] += 1\n",
    "            print(i, favorite[i])\n",
    "\n",
    "        ans = 0\n",
    "        line_len = [0 for _ in range(n)]  # 线性\n",
    "        \n",
    "        de = deque()\n",
    "        # 初始叶子节点\n",
    "        for i in range(n):\n",
    "            if rank[i] == 0:\n",
    "                de.append(i)\n",
    "                # line_len[i] = 1\n",
    "\n",
    "        while de:\n",
    "            t = de.popleft()\n",
    "            for child in edge[t]:\n",
    "                rank[child] -= 1\n",
    "                if rank[child] == 0:\n",
    "                    de.append(child)\n",
    "                line_len[child] = max(line_len[child], line_len[t] + 1)    \n",
    "                # ans = max(line_len[child], ans)\n",
    "\n",
    "\n",
    "        two_site = 0\n",
    "        finded = [0 for _ in range(n)]\n",
    "        def dfs(root):\n",
    "            finded[root] = 1\n",
    "            if finded[favorite[root]] == 1:\n",
    "                return 1\n",
    "            temp = dfs(favorite[root]) + 1\n",
    "            return temp\n",
    "\n",
    "        for i in range(n):\n",
    "            if rank[i] and finded[i] == 0:\n",
    "                temp = dfs(i)\n",
    "                ans = max(temp, ans)\n",
    "                if temp == 2:\n",
    "                    two_site += line_len[i] + line_len[favorite[i]] + 2\n",
    "                else:\n",
    "                    line_len[i] = 0\n",
    "        return max(ans, two_site)\n",
    "\n",
    " \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n = len(favorite)\n",
    "        indeg = [0] * n\n",
    "        for f in favorite:\n",
    "            indeg[f] += 1\n",
    "        \n",
    "        rg = [[] for _ in range(n)]\n",
    "        q = deque(i for i, d in enumerate(indeg) if d == 0)\n",
    "        while q:\n",
    "            now = q.popleft()\n",
    "            like = favorite[now]\n",
    "            rg[like] += [now]\n",
    "            indeg[like] -= 1\n",
    "            if indeg[like] == 0:\n",
    "                q.append(like)\n",
    "        \n",
    "        def rgdfs(now: int) -> int:\n",
    "            max_d = 1\n",
    "            for son in rg[now]:\n",
    "                max_d = max(max_d, rgdfs(son) + 1)\n",
    "            return max_d\n",
    "        \n",
    "        max_ring = sum_chain = 0\n",
    "        for i, d in enumerate(indeg):\n",
    "            if d == 0:\n",
    "                continue\n",
    "            indeg[i] = 0\n",
    "            now_ring = 1\n",
    "            now = favorite[i]\n",
    "            while now != i:\n",
    "                indeg[now] = 0\n",
    "                now_ring += 1\n",
    "                now = favorite[now]\n",
    "            \n",
    "            if now_ring == 2:\n",
    "                sum_chain += rgdfs(i) + rgdfs(favorite[i])\n",
    "            else:\n",
    "                max_ring = max(max_ring, now_ring)\n",
    "        return max(max_ring, sum_chain)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n = len(favorite)\n",
    "        deg = [0] * n\n",
    "        for f in favorite:\n",
    "            deg[f] += 1 # 统计基环树每个节点的入度\n",
    "\n",
    "        rg = [[] for _ in range(n)] # 反图\n",
    "        q = deque(i for i , d in enumerate(deg) if d == 0)\n",
    "        while q: # 拓扑排序，减掉树上所有树枝\n",
    "            x = q.popleft()\n",
    "            y = favorite[x]\n",
    "            rg[y].append(x)\n",
    "            deg[y] -= 1\n",
    "            if deg[y] == 0:\n",
    "                q.append(y)\n",
    "        \n",
    "        # 通过反图 rg寻找树枝上最深的链\n",
    "        def rdfs(x: int) -> int:\n",
    "            res = 1\n",
    "            for y in rg[x]:\n",
    "                res = max(res, rdfs(y) + 1)\n",
    "            return res\n",
    "\n",
    "        max_ring_size = sum_chain_size = 0\n",
    "        for i, d in enumerate(deg):\n",
    "            if d == 0:\n",
    "                continue\n",
    "\n",
    "            # 遍历基环上的点\n",
    "            deg[i] = 0 # 将基环上的点的入度标记为0，避免重复访问\n",
    "            ring_size = 1\n",
    "            x = favorite[i]\n",
    "            while x != i:\n",
    "                deg[x] = 0\n",
    "                ring_size += 1\n",
    "                x = favorite[x]\n",
    "            if ring_size == 2:\n",
    "                sum_chain_size += rdfs(i) + rdfs(favorite[i])\n",
    "            else:\n",
    "                max_ring_size = max(max_ring_size, ring_size)\n",
    "        return max(max_ring_size, sum_chain_size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n = len(favorite)\n",
    "        deg = [0] * n\n",
    "        for f in favorite:\n",
    "            deg[f] += 1  # 统计基环树每个节点的入度\n",
    "\n",
    "        rg = [[] for _ in range(n)]  # 反图\n",
    "        q = deque(i for i, d in enumerate(deg) if d == 0)\n",
    "        while q:  # 拓扑排序，剪掉图上所有树枝\n",
    "            x = q.popleft()\n",
    "            y = favorite[x]  # x 只有一条出边\n",
    "            rg[y].append(x)\n",
    "            deg[y] -= 1\n",
    "            if deg[y] == 0:\n",
    "                q.append(y)\n",
    "\n",
    "        # 通过反图 rg 寻找树枝上最深的链\n",
    "        def rdfs(x: int) -> int:\n",
    "            max_depth = 1\n",
    "            for son in rg[x]:\n",
    "                max_depth = max(max_depth, rdfs(son) + 1)\n",
    "            return max_depth\n",
    "\n",
    "        max_ring_size = sum_chain_size = 0\n",
    "        for i, d in enumerate(deg):\n",
    "            if d == 0: continue\n",
    "\n",
    "            # 遍历基环上的点\n",
    "            deg[i] = 0  # 将基环上的点的入度标记为 0，避免重复访问\n",
    "            ring_size = 1  # 基环长度\n",
    "            x = favorite[i]\n",
    "            while x != i:\n",
    "                deg[x] = 0  # 将基环上的点的入度标记为 0，避免重复访问\n",
    "                ring_size += 1\n",
    "                x = favorite[x]\n",
    "\n",
    "            if ring_size == 2:  # 基环长度为 2\n",
    "                sum_chain_size += rdfs(i) + rdfs(favorite[i])  # 累加两条最长链的长度\n",
    "            else:\n",
    "                max_ring_size = max(max_ring_size, ring_size)  # 取所有基环长度的最大值\n",
    "        return max(max_ring_size, sum_chain_size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n = len(favorite)\n",
    "        deg = [0] * n\n",
    "        rg = [[] for _ in range(n)]\n",
    "        for x, y in enumerate(favorite):\n",
    "            rg[y].append(x)\n",
    "            deg[y] += 1\n",
    "\n",
    "        q = deque(i for i, d in enumerate(deg) if d == 0)\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            y = favorite[x]\n",
    "            deg[y] -= 1\n",
    "            if deg[y] == 0:\n",
    "                q.append(y)\n",
    "\n",
    "        def rdfs(x: int) -> int:\n",
    "            m_depth = 1\n",
    "            for y in rg[x]:\n",
    "                if deg[y] == 0:\n",
    "                    m_depth = max(m_depth, rdfs(y) + 1)\n",
    "            return m_depth\n",
    "\n",
    "        \n",
    "        max_ring_size = sum_chine_size = 0\n",
    "        for i, d in enumerate(deg):\n",
    "            if d <= 0:\n",
    "                continue\n",
    "            res = 0\n",
    "            x = i\n",
    "            while True:\n",
    "                res += 1\n",
    "                deg[x] = -1\n",
    "                x = favorite[x]\n",
    "                if x == i:\n",
    "                    break\n",
    "            if res == 2:\n",
    "                sum_chine_size += rdfs(i) + rdfs(favorite[i])\n",
    "            else:\n",
    "                max_ring_size = max(max_ring_size, res)\n",
    "        \n",
    "        return max(max_ring_size, sum_chine_size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        #答案分为两种情况： \n",
    "        #1. 有一对互相喜欢的员工， 这时候可以求员工1， 2 后边分别有多少个员工喜欢 （形成两条链）， 这两条链长即为答案\n",
    "        #2. 有一个环， 环长即为答案\n",
    "        #要注意如果只有一条链是不行的， 因为链首没有喜欢的人\n",
    "        #每个点相连形成的图为一个内向基环树， 因为每个点只有一条出边\n",
    "        #建一个反图， 还是拓扑排序， 不过原来找入度为0变成了找出度为0， 出度的from其实就是原来的to， 可以直接通过favorite找到\n",
    "        n = len(favorite)\n",
    "        outdeg = [0] * n\n",
    "        rg = [[] for _ in range(n)]\n",
    "        for x, y in enumerate(favorite):\n",
    "            rg[y].append(x)\n",
    "            outdeg[y] += 1\n",
    "        dq = deque([i for i in range(n) if outdeg[i] == 0])\n",
    "        while dq:\n",
    "            y = dq.popleft()\n",
    "            x = favorite[y]\n",
    "            outdeg[x] -= 1\n",
    "            if outdeg[x] == 0:\n",
    "                dq.append(x)\n",
    "        v = set()\n",
    "        ans = 0\n",
    "        cyc_ans = 0\n",
    "        cyc_link = 0\n",
    "        def dfs(x):\n",
    "            cur = 1\n",
    "            for y in rg[x]:\n",
    "                cur = max(cur, 1 + dfs(y))\n",
    "            return cur\n",
    "        print(rg)\n",
    "        #剩下的就是环, 遍历每个环\n",
    "        for i in range(n):\n",
    "            if outdeg[i] == 0 or i in v:\n",
    "                continue\n",
    "            sz = set()\n",
    "            x = i\n",
    "            while x not in sz:\n",
    "                sz.add(x)\n",
    "                rg[favorite[x]].remove(x)\n",
    "                x = favorite[x]\n",
    "            v |= sz\n",
    "            if len(sz) == 2:\n",
    "                ans1 = 0\n",
    "                for _ in range(2):\n",
    "                    x = sz.pop()\n",
    "                    ans1 += dfs(x)\n",
    "                cyc_link += ans1\n",
    "            elif len(sz) > 2:\n",
    "                ans = max(ans, len(sz))\n",
    "\n",
    "        return max(ans, cyc_link)\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        nlen = len(favorite)\n",
    "        result = 0\n",
    "\n",
    "        # Find out the loop pair\n",
    "        accessed = [0 for _ in range(nlen)]\n",
    "        pairs = []\n",
    "        for i in range(nlen):\n",
    "            if accessed[i]:\n",
    "                continue\n",
    "            if favorite[favorite[i]] == i:\n",
    "                pairs.append([i, favorite[i]])\n",
    "                accessed[i], accessed[favorite[i]] = 1, 1\n",
    "\n",
    "        # Construct the follower array.\n",
    "        liked = [[] for _ in range(nlen)]\n",
    "        for i in range(nlen):\n",
    "            liked[favorite[i]].append(i)\n",
    "\n",
    "        # DFS to find the longest follower list (named as tail below)\n",
    "        tails_len = [0 for _ in range(nlen)]\n",
    "\n",
    "        def dfs(n, excluded=None):\n",
    "            # excluded argumetn to exclude its pair from search scope.\n",
    "            nonlocal tails_len\n",
    "            # max_tail_len = 0\n",
    "            if not liked[n]:\n",
    "                return\n",
    "            for i in liked[n]:\n",
    "                if i == excluded:\n",
    "                    continue\n",
    "                dfs(i)\n",
    "                tails_len[n] = max(tails_len[n], 1 + tails_len[i])\n",
    "\n",
    "        for pair in pairs:\n",
    "            dfs(pair[0], pair[1])\n",
    "            dfs(pair[1], pair[0])\n",
    "            result = result + 2 + tails_len[pair[0]] + tails_len[pair[1]]\n",
    "\n",
    "\n",
    "        # Search for the close loop if any.\n",
    "        accessed = [[0,-1] for _ in range(nlen)]\n",
    "        loop_cnt = 0\n",
    "        for i in range(nlen):\n",
    "            loop_cnt += 1\n",
    "            cur = i\n",
    "            if accessed[i][0] != 0:\n",
    "                continue\n",
    "            accessed[cur][0] = loop_cnt\n",
    "            accessed[cur][1] = 0\n",
    "            \n",
    "            while 1:\n",
    "                like = favorite[cur]\n",
    "\n",
    "                if accessed[like][0] == 0:\n",
    "                    accessed[like][1] = accessed[cur][1] + 1\n",
    "                    accessed[like][0] = loop_cnt\n",
    "                    cur = like\n",
    "                elif accessed[like][0] == loop_cnt:\n",
    "                    result = max(result, accessed[cur][1] - accessed[like][1] + 1)\n",
    "                    break\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        \"\"\" 分类讨论 pseudotree的情况 \n",
    "        if pseudotree(circle) size > 2: maxRingSize = pseudotree size \n",
    "        if pseudotree(circle) size = 2: 对每个pseudotree的node反向找链, \n",
    "        对于多个基环长度等于2的基环树，每个基环树所对应的链，都可以拼在其余链的末尾，\n",
    "        因此可以将这些链全部拼成一个圆桌，其大小记作sumChainSize\n",
    "        ==> max(maxRingSize, sumChainSize)\n",
    "        \"\"\"\n",
    "\n",
    "        # reversely-directed rG, doesn't influence the circle \n",
    "        # the dfs will need to be rdfs  \n",
    "        rG = collections.defaultdict(list)\n",
    "        n = len(favorite)\n",
    "        indeg = [0] * n \n",
    "        for i in favorite:\n",
    "            indeg[i] += 1 \n",
    "\n",
    "        # make the rG and also pruning the indeg\n",
    "        # pseudotree nodes have indeg = 1, all leaf nodes have indeg = 0 \n",
    "        queue = collections.deque([i for i, j in enumerate(indeg) if not indeg[i]])\n",
    "        while queue:\n",
    "            u = queue.popleft()\n",
    "            v = favorite[u]\n",
    "            rG[v].append(u) \n",
    "            indeg[v] -= 1 \n",
    "            if not indeg[v]: \n",
    "                queue.append(v) \n",
    "\n",
    "        # reverse DFS, get the depth of chain from each of the two nodes \n",
    "        def rdfs(x):\n",
    "            max_ = 1 \n",
    "            for v in rG[x]:\n",
    "                max_ = max(rdfs(v)+1, max_) \n",
    "            return max_ \n",
    "\n",
    "        maxRingSize, sumChainSize = 0, 0 \n",
    "        for u, d in enumerate(indeg):\n",
    "            # only search for the pesudotree nodes \n",
    "            if d == 0:\n",
    "                continue \n",
    "\n",
    "            indeg[u] = 0  # vis array \n",
    "            temp_ringsize = 1\n",
    "            x = favorite[u] \n",
    "            while x != u:\n",
    "                indeg[x] = 0  # vis array \n",
    "                temp_ringsize += 1 \n",
    "                x = favorite[x] \n",
    "            \n",
    "            if temp_ringsize == 2:  # combine rdfs results \n",
    "                sumChainSize += rdfs(u) + rdfs(favorite[u]) \n",
    "            else:\n",
    "                maxRingSize = max(maxRingSize, temp_ringsize)\n",
    "\n",
    "        return max(maxRingSize, sumChainSize)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        g = defaultdict(list) \n",
    "        n = len(favorite)\n",
    "        indeg = [0] * n \n",
    "        for i in range(n):\n",
    "            g[i].append(favorite[i]) \n",
    "            indeg[favorite[i]] += 1 \n",
    "        circle = [1] * n \n",
    "        D = [0] * n \n",
    "        Q = deque()\n",
    "        for i in range(n):\n",
    "            if indeg[i] == 0:\n",
    "                Q.append(i)\n",
    "        \n",
    "        while Q:\n",
    "            u = Q.popleft()\n",
    "            circle[u] = 0 \n",
    "            for v in g[u]:\n",
    "                indeg[v] -= 1\n",
    "                D[v] = max(D[v], D[u] + 1) \n",
    "                if indeg[v] == 0:\n",
    "                    Q.append(v)\n",
    "        vis = [0] * n \n",
    "        def dfs(u):\n",
    "            vis[u] = 1 \n",
    "            tot = 1 \n",
    "            for v in g[u]:\n",
    "                if not vis[v]:\n",
    "                    tot += dfs(v) \n",
    "            return tot \n",
    "        ans = 0 \n",
    "        mx = 0 \n",
    "        for i in range(n):\n",
    "            if circle[i] == 1 and not vis[i]: \n",
    "                x = dfs(i)\n",
    "                mx = max(mx, x) \n",
    "                if x == 2:\n",
    "                    ans += 2 + D[i] + D[g[i][0]] \n",
    "        return max(ans, mx) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''必须存在成环状或者存在互相喜欢才能有人参加'''\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, favorite: List[int]) -> int:\n",
    "        n=len(favorite)\n",
    "        g=[[] for _ in range(n)]\n",
    "        for i,x in enumerate(favorite):\n",
    "            g[x].append(i)\n",
    "\n",
    "\n",
    "        def dfs(cur:int,pa:int)->int:\n",
    "            if cur==pa:return -inf\n",
    "            ret=0\n",
    "            for nxt in g[cur]:\n",
    "                ret=max(ret,dfs(nxt,pa))\n",
    "            return ret+1\n",
    "        \n",
    "        ans1=ans2=0 #ans1：大于等于3的环状链。ans2:相互喜欢的人数对。（三人以上成环状）与（相互喜欢+各自被单恋的舔狗人数）互斥\n",
    "        attended=set()\n",
    "        vis=[False]*n   #标记已经检索过的发起人\n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                vis[i]=True\n",
    "                path=1\n",
    "                if not vis[favorite[i]]:\n",
    "                    next=favorite[i]\n",
    "                    while not vis[next]:#未检索的员工进行标记，并获得有效的暗恋链长度\n",
    "                        path+=1\n",
    "                        vis[next]=True\n",
    "                        next=favorite[next]\n",
    "                    enter=next\n",
    "                    next=favorite[enter]\n",
    "                    cnt=1\n",
    "                    while enter!=next and cnt<2*path:   #找环状成员，第二个比较用来防止陷入死循环\n",
    "                        next=favorite[next]\n",
    "                        cnt+=1\n",
    "                    if cnt<=path and next not in attended:  #该暗恋环未被统计且属于有效环\n",
    "                        attended.add(next)\n",
    "                        if next==favorite[favorite[next]]:\n",
    "                            attended.add(favorite[next])\n",
    "                            a=max(0,dfs(next,favorite[next])-1)\n",
    "                            b=max(0,dfs(favorite[next],next)-1)\n",
    "                            ans1+=2+a+b\n",
    "                        else:\n",
    "                            start=next\n",
    "                            next=favorite[next]\n",
    "                            steps=1\n",
    "                            while next!=start:\n",
    "                                attended.add(next)\n",
    "                                next=favorite[next]\n",
    "                                steps+=1\n",
    "                            ans2=max(ans2,steps)\n",
    "\n",
    "        return max(ans1,ans2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        avails_map = [[j for j in range(n) if grid[i][j]] for i in range(m)]\n",
    "        match = [-1] * n\n",
    "        # visits = [False] * n\n",
    "\n",
    "        def dfs(i):\n",
    "            for j in avails_map[i]:\n",
    "                if not visits[j] and match[j] == -1:\n",
    "                    match[j] = i \n",
    "                    return True \n",
    "            \n",
    "            for j in avails_map[i]:\n",
    "                if not visits[j]:\n",
    "                    visits[j] = True\n",
    "                    if dfs(match[j]):\n",
    "                        match[j] = i \n",
    "                        return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            visits = [False] * n \n",
    "            if dfs(i):\n",
    "                ans += 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        avails_map = [[j for j in range(n) if grid[i][j]] for i in range(m)]\n",
    "        match = [-1] * n\n",
    "        # visits = [False] * n\n",
    "\n",
    "        def dfs(i):\n",
    "            for j in avails_map[i]:\n",
    "                if not visits[j] and match[j] == -1:\n",
    "                    match[j] = i \n",
    "                    return True \n",
    "            \n",
    "            for j in avails_map[i]:\n",
    "                if not visits[j]:\n",
    "                    visits[j] = True\n",
    "                    if dfs(match[j]):\n",
    "                        match[j] = i \n",
    "                        return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            visits = [False] * n \n",
    "            if dfs(i):\n",
    "                ans += 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        avails_map = [[j for j in range(n) if grid[i][j]] for i in range(m)]\n",
    "        match = [-1] * n\n",
    "        # visits = [False] * n\n",
    "\n",
    "        def dfs(i):\n",
    "            for j in avails_map[i]:\n",
    "                if not visits[j] and match[j] == -1:\n",
    "                    match[j] = i \n",
    "                    return True \n",
    "            \n",
    "            for j in avails_map[i]:\n",
    "                if not visits[j]:\n",
    "                    visits[j] = True\n",
    "                    if dfs(match[j]):\n",
    "                        match[j] = i \n",
    "                        return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            visits = [False] * n \n",
    "            if dfs(i):\n",
    "                ans += 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pa = [-1] * n \n",
    "        def match(i,vis):\n",
    "            #vis[] = 1\n",
    "            for j in range(n):\n",
    "                if grid[i][j] and not vis[j]:\n",
    "                    vis[j] = 1\n",
    "                    if pa[j] == -1 or match(pa[j],vis):\n",
    "                        pa[j] = i \n",
    "                        return True \n",
    "            return False\n",
    "        cnt = 0  \n",
    "        for i in range(m):\n",
    "            vis = [0] * n \n",
    "            if match(i, vis):\n",
    "                cnt += 1\n",
    "        return cnt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        avails_map = [[j for j in range(n) if grid[i][j]] for i in range(m)]\n",
    "        match = [-1] * n\n",
    "        # visits = [False] * n\n",
    "\n",
    "        def dfs(i):\n",
    "            # for j in avails_map[i]:\n",
    "            #     if not visits[j] and match[j] == -1:\n",
    "            #         match[j] = i \n",
    "            #         return True \n",
    "            \n",
    "            for j in avails_map[i]:\n",
    "                if not visits[j]:\n",
    "                    visits[j] = True\n",
    "                    if match[j] == -1 or dfs(match[j]):\n",
    "                        match[j] = i \n",
    "                        return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            visits = [False] * n \n",
    "            if dfs(i):\n",
    "                ans += 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        ad=collections.defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    ad[i].append(j)\n",
    "        \n",
    "        match=[-1]*n\n",
    "        vis=[False]*n\n",
    "        def dfs(cur):\n",
    "            for nex in ad[cur]:\n",
    "                if vis[nex]==False:\n",
    "                    vis[nex]=True\n",
    "                    if match[nex]==-1 or dfs(match[nex]):\n",
    "                        match[nex]=cur\n",
    "                        return True \n",
    "            return False\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            vis=[False]*n\n",
    "            if dfs(i):\n",
    "                ans+=1\n",
    "    \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        ad=collections.defaultdict(list)\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    ad[i].append(j)\n",
    "        match=[-1]*n\n",
    "        vis=[False]*n\n",
    "        def dfs(i):\n",
    "            for j in ad[i]:\n",
    "                if not vis[j]:\n",
    "                    vis[j]=True\n",
    "                    if match[j]==-1 or dfs(match[j]):\n",
    "                        match[j]=i\n",
    "                        return True\n",
    "            return False\n",
    "        for i in range(m):\n",
    "            vis=[False]*n\n",
    "            if dfs(i):\n",
    "                ans+=1\n",
    "        return ans \n",
    "\n",
    "\n",
    "        dfs(0,0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        avails_map = [[j for j in range(n) if grid[i][j]] for i in range(m)]\n",
    "        match = [-1] * n\n",
    "        # visits = [False] * n\n",
    "\n",
    "        def dfs(i):\n",
    "            # for j in avails_map[i]:\n",
    "            #     if not visits[j] and match[j] == -1:\n",
    "            #         match[j] = i \n",
    "            #         return True \n",
    "            \n",
    "            for j in avails_map[i]:\n",
    "                if not visits[j]:\n",
    "                    visits[j] = True\n",
    "                    if match[j] == -1 or dfs(match[j]):\n",
    "                        match[j] = i \n",
    "                        return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            visits = [False] * n \n",
    "            if dfs(i):\n",
    "                ans += 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, grid: List[List[int]]) -> int:\n",
    "        dc = defaultdict(list)\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    dc[i].append(j)\n",
    "        pa, pb = [-1] * n, [-1] * n\n",
    "        def xyl(x):\n",
    "            if x == -1: return True\n",
    "            for i in dc[x]:\n",
    "                if s[i]:\n",
    "                    s[i] = 0\n",
    "                    if xyl(pb[i]):\n",
    "                        pb[i] = x\n",
    "                        return True\n",
    "            return False\n",
    "            \n",
    "        for i in range(m):\n",
    "            s = [1] * n\n",
    "            xyl(i)\n",
    "            # print(pb, s)\n",
    "        return sum(i!=-1 for i in pb)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 匈牙利算法\n",
    "# https://cloud.tencent.com/developer/article/1525214\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, grid: List[List[int]]) -> int:\n",
    "        # 建图\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dct = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    dct[i].append(j)\n",
    "\n",
    "        # 匈牙利算法\n",
    "        match = [-1] * n\n",
    "        def hungarian(i):\n",
    "            for j in dct[i]:\n",
    "                if not visit[j]:\n",
    "                    visit[j] = True\n",
    "                    if match[j] == -1 or hungarian(match[j]):\n",
    "                        match[j] = i\n",
    "                        return True\n",
    "\n",
    "            return False\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            visit = [False] * n\n",
    "            if hungarian(i):\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        match=[-1 for _ in range(n)]\n",
    "        def find(x):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] and state[y] == False: \n",
    "                    state[y] = True \n",
    "                    if match[y] == -1 or find(match[y]):\n",
    "                        match[y] = x\n",
    "                        return True \n",
    "            return False \n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            state=[False]*n\n",
    "            if find(i):\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if m == 0 or n == 0:\n",
    "            return 0\n",
    "        graph = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    graph[i].append(j)\n",
    "        match = [-1] * n\n",
    "\n",
    "        def hangarian(i, visited):\n",
    "            nonlocal match\n",
    "            for j in graph[i]:\n",
    "                if visited[j] is False:\n",
    "                    visited[j] = True\n",
    "                    if match[j] == -1 or hangarian(match[j], visited):\n",
    "                        match[j] = i\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        result = 0\n",
    "        for i in range(m):\n",
    "            if hangarian(i, [False] * n):\n",
    "                result += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, g: List[List[int]]) -> int:\n",
    "        n, m = len(g), len(g[0])\n",
    "        \n",
    "        p = [-1] * m\n",
    "        vis = [0] * m\n",
    "        def find(x):\n",
    "            for y in range(m):\n",
    "                if g[x][y] and not vis[y]:\n",
    "                    vis[y] = 1\n",
    "                    if p[y] == -1 or find(p[y]):\n",
    "                        p[y] = x\n",
    "                        return 1\n",
    "            return 0\n",
    "        ans = 0\n",
    "        for x in range(n):\n",
    "            vis = [0] * m\n",
    "            ans += find(x)\n",
    "        return ans\n",
    "        \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumInvitations(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        link = [-1] * n\n",
    "        vis = set()\n",
    "        def hungry():\n",
    "            cnt = 0\n",
    "            for u in range(m):\n",
    "                vis.clear()\n",
    "                cnt += dfs(u)\n",
    "            return cnt\n",
    "        def dfs(u):\n",
    "            for v in range(n):\n",
    "                if grid[u][v] and v not in vis:\n",
    "                    vis.add(v)\n",
    "                    if link[v] == -1 or dfs(link[v]):\n",
    "                        link[v] = u\n",
    "                        return 1\n",
    "            return 0\n",
    "        return hungry()\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
